LeetCode——有关递归的相关题目

最近发现自己并没有真正理解递归&＃xff0c;于是重新把递归的相关题目又重新做了一遍&＃xff0c;参考了http://39.96.217.32/blog/4#comment-container讲解&＃xff0c;很受用

111. 二叉树的最小深度

这道题有一个陷阱就是当根节点只有左子树或者只有右子树的时候&＃xff0c;最小深度是2&＃xff0c;而不是1&＃xff0c;所以我决定单独判断这两种情况

/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode(int x) { val &＃61; x; }* }*/
class Solution {// int left &＃61; 0;// int right &＃61; 0;public int minDepth(TreeNode root) {if(root &＃61;&＃61; null)return 0;if(root.left &＃61;&＃61; null&&root.right &＃61;&＃61; null)return 1;if(root.left &＃61;&＃61; null)return minDepth(root.right)&＃43;1;if(root.right &＃61;&＃61;null)return minDepth(root.left)&＃43;1;return 1&＃43;Math.min(minDepth(root.left),minDepth(root.right));}
}

101. 对称二叉树

这道题剑指offer中也有&＃xff0c;应该在写一个判断两个树中对应结点&＃xff0c;从结构和内容两方面分别判断

/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode(int x) { val &＃61; x; }* }*/
class Solution {public boolean isSymmetric(TreeNode root) {if(root &＃61;&＃61; null)return true;return isSymmetric(root.left,root.right);}private boolean isSymmetric(TreeNode p,TreeNode q){if(p &＃61;&＃61; null&&q &＃61;&＃61; null)return true;if(p &＃61;&＃61; null||q &＃61;&＃61; null)return false;if(p.val !&＃61; q.val)return false;return isSymmetric(p.left,q.right)&&isSymmetric(p.right,q.left);}
}

110. 平衡二叉树

分为两步&＃xff0c;首先判断每个节点的最大深度&＃xff0c;其次判断每个节点是否平衡&＃xff0c;即左右子树只差的绝对值是否小于等于1

/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode(int x) { val &＃61; x; }* }*/
class Solution {public boolean isBalanced(TreeNode root) {if(root &＃61;&＃61; null)return true;return Math.abs(maxDepth(root.left) - maxDepth(root.right)) <&＃61; 1 && isBalanced(root.left) && isBalanced(root.right);}private int maxDepth(TreeNode root){if(root &＃61;&＃61; null)return 0;int left &＃61; maxDepth(root.left);int right &＃61; maxDepth(root.right);return 1&＃43;(left>right?left:right);}
}

24. 两两交换链表中的节点

将所有结点分为三部分&＃xff0c;两个即将交换的结点&＃xff0c;和已经处理完的链表

/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val &＃61; x; }* }*/
class Solution {public ListNode swapPairs(ListNode head) {if(head &＃61;&＃61; null||head.next &＃61;&＃61; null)return head;ListNode next &＃61; head.next;head.next &＃61; swapPairs(next.next);next.next &＃61; head;return next;}
}

617. 合并二叉树

/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode(int x) { val &＃61; x; }* }*/
class Solution {public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {TreeNode t &＃61; new TreeNode(0);if(t1 &＃61;&＃61; null&&t2 &＃61;&＃61;null)return null;if(t1 &＃61;&＃61; null)return t2;if(t2 &＃61;&＃61; null)return t1;if(t1!&＃61; null&&t2 !&＃61; null){t.val &＃61; t1.val&＃43;t2.val;t.left &＃61; mergeTrees(t1.left,t2.left);t.right &＃61; mergeTrees(t1.right,t2.right);}return t;}
}

226. 翻转二叉树

这道题很经典&＃xff0c;感觉以后面试会经常出现&＃xff0c;重点就是交换每个非叶节点的左右子树&＃xff0c;不用想左右子树有一个可能为null的情况

/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode(int x) { val &＃61; x; }* }*/
class Solution {public TreeNode invertTree(TreeNode root) {if(root &＃61;&＃61; null)return null;TreeNode temp &＃61; root.left;root.left &＃61; root.right;root.right &＃61; temp;if(root.left !&＃61; null)invertTree(root.left);if(root.right !&＃61; null)invertTree(root.right);return root;}
}

113. 路径总和 II

/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode(int x) { val &＃61; x; }* }*/
class Solution {List> ans &＃61; new ArrayList<>();public List> pathSum(TreeNode root, int sum) {bfs(root,new ArrayList<>(),sum);return ans;}public void bfs(TreeNode root,List temp,int sum){if(root &＃61;&＃61; null)return;temp.add(root.val);int result &＃61; sum-root.val;if(root.left &＃61;&＃61; null&&root.right &＃61;&＃61; null){if(result &＃61;&＃61; 0){ans.add(new ArrayList(temp));}}bfs(root.left,temp,result);bfs(root.right,temp,result);temp.remove(temp.size()-1);}
}

112. 路径总和

/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode(int x) { val &＃61; x; }* }*/
class Solution {public boolean hasPathSum(TreeNode root, int sum) {if(root &＃61;&＃61; null)return false;sum -&＃61; root.val;if(root.left &＃61;&＃61; null&&root.right &＃61;&＃61; null){if(sum &＃61;&＃61; 0)return true;return false;}return hasPathSum(root.left,sum)||hasPathSum(root.right,sum);}
}