递归，其实就是在运行的过程中调用自己。平时解决递归三部曲，可以考虑下：
找整个递归的终止条件：递归应该在什么时候结束？
找返回值：应该给上一级返回什么信息？
本级递归应该做什么：在这一级递归中，应该完成什么任务？
构成递归需具备的条件：
- 子问题须与原始问题为同样的事，且更为简单；
- 不能无限制地调用本身，须有个出口，化简为非递归状况处理。
112. 路径总和
题目描述：
给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。
说明: 叶子节点是指没有子节点的节点。
示例:
给定如下二叉树，以及目标和 sum = 22，
5
/ \
4 8
/ / \
11 13 4
/ \ \
7 2 1返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。
解题思路：
递归遍历整棵树：如果当前节点不是叶子，对它的所有孩子节点，递归调用 hasPathSum 函数，其中 sum 值减去当前节点的权值；
时间复杂度：每访问每个节点一次，时间复杂度为 O(N)O(N) ，其中 NN 是节点个数
空间复杂度：
最坏情况下，整棵树是非平衡的，例如每个节点都只有一个孩子，递归会调用 NN 次（树的高度），因此栈的空间开销是 O(N)O(N)
最好情况下，树是完全平衡的，高度只有 \log(N)log(N)，因此在这种情况下空间复杂度只有 O(\log(N))O(log(N))
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public static int res = 0;
public boolean hasPathSum(TreeNode root, int sum) {
if (root == null) return false;
if (root.left == null && root.right == null && root.val == sum) return true;
return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
}
}111. 二叉树的最小深度
题目描述：
给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明: 叶子节点是指没有子节点的节点。
示例:
给定二叉树 [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回它的最小深度 2.解题思路：
这里注意 叶子节点是指没有子节点的节点，然后当 root 节点左右孩子有一个为空时，返回不为空的孩子节点的深度，当 root 节点左右孩子都不为空时，返回左右孩子较小深度的节点值。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public int minDepth(TreeNode root) {
if (root == null) return 0;
int left = minDepth(root.left);
int right = minDepth(root.right);
if (left == 0 || right == 0) return left + right + 1;
return Math.min(left,right)+1;
}
}617. 合并二叉树
题目描述：
给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明: 叶子节点是指没有子节点的节点。
示例:
给定二叉树 [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回它的最小深度 2.
##### 解题思路：
给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。
你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。解题思路：
首先先判断t1是否为空，如果为空返回t2；如果t2为空则返回t1 当前面的if语句都没运行那么证明两方都不为空。那么先将两节点的值相加，然后再递归左节点，递归右节点。需要注意的就是需要创建临时节点root。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
if (t1 == null && t2 == null) return null;
if (t1 == null) return t2;
if (t2 == null) return t1;
TreeNode root = new TreeNode(t1.val + t2.val);
root.left = mergeTrees(t1.left, t2.left);
root.right = mergeTrees(t1.right, t2.right);
return root;
}
}437. 路径总和 III
题目描述：
给定一个二叉树，它的每个结点都存放着一个整数值。
找出路径和等于给定数值的路径总数。
路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。
二叉树不超过1000个节点，且节点数值范围是 [-1000000,1000000] 的整数。
示例：
root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8
10
/ \
5 -3
/ \ \
3 2 11
/ \ \
3 -2 1
返回 3。和等于 8 的路径有:
1. 5 -> 3
2. 5 -> 2 -> 1
3. -3 -> 11解题思路：
递归求解树的问题必然是要遍历整棵树的，所以二叉树的遍历框架必然要出现在主函数 pathSum 中。
这道题中 其中
count(root,sum) 为自己为开头的路径数
pathSum(root.left,sum) 左边路径总数
pathSum(root.right,sum) 右边路径总数
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public int pathSum(TreeNode root, int sum) {
if (root == null) return 0;
return count(root,sum) + pathSum(root.left,sum) + pathSum(root.right,sum);
}
private int count(TreeNode root,int sum) {
if (root == null) return 0;
int res = 0;
if (root.val == sum) res++;
res += count(root.left,sum - root.val) + count(root.right,sum - root.val);
return res;
}
}
572. 另一个树的子树
题目描述：
给定两个非空二叉树 s 和 t，检验 s 中是否包含和 t 具有相同结构和节点值的子树。s 的一个子树包括 s 的一个节点和这个节点的所有子孙。s 也可以看做它自身的一棵子树。
示例 1:
给定的树 s:
3
/ \
4 5
/ \
1 2
给定的树 t：
4
/ \
1 2
返回 true，因为 t 与 s 的一个子树拥有相同的结构和节点值。解题思路：
跟LeetCode 437 题有点类似，同样写一个递归方法 isRoot ，该方法用来判断两个节点值是否相等(包括它们的左右子树)，然后在 isSubtree 中 递归调用左右子树判断即可。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isSubtree(TreeNode s, TreeNode t) {
if (s == null) return false;
return isRoot(s,t) || isSubtree(s.left,t) || isSubtree(s.right,t);
}
private boolean isRoot(TreeNode t1, TreeNode t2) {
if (t1 == null && t2 == null) return true;
if (t1 == null || t2 == null) return false;
if (t1.val != t2.val) return false;
return isRoot(t1.left,t2.left) && isRoot(t1.right,t2.right);
}
}101. 对称二叉树
题目描述：
给定一个二叉树，检查它是否是镜像对称的。
例如，二叉树 [1,2,2,3,4,4,3] 是对称的。
1
/ \
2 2
/ \ / \
3 4 4 3
但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:
1
/ \
2 2
\ \
3 3解题思路：
其实跟上面题差不多，就是递归判断左右子树是否相等，subSymmetric 方法，就是判断子树中的值是否相同，本题也可以用栈迭代的方法来解题。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isSymmetric(TreeNode root) {
if (root == null) return true;
return subSymmetric(root.left,root.right);
}
private boolean subSymmetric(TreeNode t1,TreeNode t2) {
if (t1 == null && t2 == null) return true;
if (t1 == null || t2 == null) return false;
if (t1.val != t2.val) return false;
return subSymmetric(t1.left,t2.right) && subSymmetric(t1.right,t2.left);
}
}404. 左叶子之和
题目描述：
计算给定二叉树的所有左叶子之和。
示例：
3
/ \
9 20
/ \
15 7
在这个二叉树中，有两个左叶子，分别是 9 和 15，所以返回 24解题思路：
首先写一个判断是不是叶子结点的方法，然后在主方法递归调用根节点的左右节点 然后累加sum。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
private int sum = 0;
public int sumOfLeftLeaves(TreeNode root) {
if (root == null) return 0;
if (isLeaf(root.left)) sum += root.left.val;
sumOfLeftLeaves(root.left);
sumOfLeftLeaves(root.right);
return sum;
}
private boolean isLeaf(TreeNode t) {
if (t == null) return false;
if (t.left == null && t.right == null) return true;
return false;
}
}
