剑指Offer之Java算法习题精讲链表与二叉树专项训练

题目一

链表题——反转链表

根据单链表的头节点head来返回反转后的链表

具体题目如下

解法

/**
* Definition for singly-linked list.
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode() {}
*     ListNode(int val) { this.val = val; }
*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
   public ListNode reverseList(ListNode head) {
       ListNode pre,cur,nxt;
       pre = null;
       cur = head;
       nxt = head;
       while(cur!=null){
           nxt = cur.next;
           cur.next = pre;
           pre = cur;
           cur = nxt;
       }
       return pre;
   }
}

题目二

链表题——反转链表

按照一定数量的节点来进行反转并返回反转之后的链表

具体题目如下

解法

/**
* Definition for singly-linked list.
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode() {}
*     ListNode(int val) { this.val = val; }
*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
   public ListNode reverseKGroup(ListNode head, int k) {
        if (head == null) return null;
        ListNode a, b;
        a = b = head;
        for (int i = 0; i < k; i++) {
           if (b == null) return head;
            b = b.next;
        }
        ListNode newHead = reverse(a, b);
        a.next = reverseKGroup(b, k);
        return newHead;
   }
   ListNode reverse(ListNode a, ListNode b) {
       ListNode pre,cur,nxt;
       pre = null;
       cur = a;
       nxt = a;
       while(cur!=b){
           nxt = cur.next;
           cur.next = pre;
           pre = cur;
           cur = nxt;
       }
       return pre;
   }
}

题目三

链表题&mdash;&mdash;回文链表

根据单链表的头节点head来判断该链表是否是回文链表，并返回结果

具体题目如下

解法：后序遍历与left比较

/**
* Definition for singly-linked list.
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode() {}
*     ListNode(int val) { this.val = val; }
*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
   ListNode left;
   public boolean isPalindrome(ListNode head) {
       left = head;
       return traverse(head);
   }
   boolean traverse(ListNode right){
       if (right == null) return true;
       boolean res = traverse(right.next);
       res = res && (right.val == left.val);
       left = left.next;
       return res;
   }
}

题目四

二叉树题&mdash;&mdash;翻转二叉树

根据所给的二叉树根节点root来翻转此二叉树，并返回翻转后的二叉树根节点

具体题目如下

 解法

/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode() {}
*     TreeNode(int val) { this.val = val; }
*     TreeNode(int val, TreeNode left, TreeNode right) {
*         this.val = val;
*         this.left = left;
*         this.right = right;
*     }
* }
*/
class Solution {
   public TreeNode invertTree(TreeNode root) {
       if(root==null){
           return null;
       }
       TreeNode lf = invertTree(root.left);
       TreeNode rg = invertTree(root.right);
       root.left = rg;
       root.right = lf;
       return root;
   }
}

题目五

二叉树题&mdash;&mdash;填充节点

给定一个完美二叉树，填充该二叉树每个节点的下一个右侧节点指针

具体题目如下

解法

/*
// Definition for a Node.
class Node {
   public int val;
   public Node left;
   public Node right;
   public Node next;
   public Node() {}

public Node(int _val) {
       val = _val;
   }
   public Node(int _val, Node _left, Node _right, Node _next) {
       val = _val;
       left = _left;
       right = _right;
       next = _next;
   }
};
*/

class Solution {
   public Node connect(Node root) {
       if(root==null) return null;
       method(root.left,root.right);
       return root;
   }
   public void method(Node left,Node right){
       if (left == null || right == null) {
           return;
       }
       left.next = right;
       method(left.left,left.right);
       method(right.left,right.right);
       method(left.right,right.left);
   }
}

题目六

二叉树链表题&mdash;&mdash;将二叉树展开为链表

根据给定的二叉树根节点root，将此二叉树展开为单链表

具体题目如下

解法

/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode() {}
*     TreeNode(int val) { this.val = val; }
*     TreeNode(int val, TreeNode left, TreeNode right) {
*         this.val = val;
*         this.left = left;
*         this.right = right;
*     }
* }
*/
class Solution {
   public void flatten(TreeNode root) {
       if (root == null) return;

flatten(root.left);
       flatten(root.right);

TreeNode left = root.left;
       TreeNode right = root.right;

root.left = null;
       root.right = left;

TreeNode p = root;
       while (p.right != null) {
           p = p.right;
       }
       p.right = right;
   }
}

来源：https://blog.csdn.net/wai_58934/article/details/123031314