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

剑指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;

}

}

题目三

链表题——回文链表

根据单链表的头节点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;

}

}

题目四

二叉树题——翻转二叉树

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

具体题目如下

解法

/**

* Definition for a binary tree node.

* public class TreeNode {

* int val;

* TreeNode left;

* TreeNode right;

* TreeNode() {}

* TreeNohttp://de(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;

}

}

题目五

二叉树题——填充节点

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

具体题目如下

解法

/*

// 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);

bhypldSEsF method(right.left,right.right);

method(left.right,right.left);

}

}

题目六

二叉树链表题——将二叉树展开为链表

根据给定的二叉树根节点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;

}

}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。