1、二叉树的递归结构
如何定义二叉树？二叉树是每个结点最多只有两个分支的树。这是一个正确的定义，但对解决问题没有帮助。我们需要的是二叉树的递归定义：
* 空树是一个二叉树
* 如果 和 是二叉树，那么用一个根结点连接 和 得到的也是二叉树
可以看到，二叉树天生就是递归的。遍历一个二叉树，先处理根结点，左右两个子树又是二叉树，可以递归处理。
递归本质上是将问题分解成同类的子问题，反复调用自己来进行求解。你可能更熟悉动态规划里的子问题，但实际上任何有递归函数的地方都有子问题。
许多二叉树问题都可以通过划分子问题来求解。如果我们思考出了子问题的划分方式，那么使用何种方式进行递归遍历，都是能很容易就推导出的。
2、二叉树子问题划分
递归有两大要点：* 反复调用自身 * 终止条件
而在二叉树结构上进行递归，则这两大要点变为：
* 递归调用自己两个子树
* 在叶结点处终止递归
其中，调用子树的部分是重点。我们需要保证在子树上求解的是与原问题相同的子问题，才能递归调用自身。而终止条件可以放在最后作为细节考虑。
例题：给定一个二叉树和一个目标和，判断该树中是否存在根结点到叶结点的路径，这条路径上所有结点值相加等于目标和。
boolean hasPathSum(TreeNode root, int sum) {
if (root == null) {
return false;
}
if (root.left == null && root.right == null) {
return root.val == sum;
}
int target = sum - root.val;
return hasPathSum(root.left, target)
|| hasPathSum(root.right, target);
}
一个小经验是：凡是题目描述里提到叶结点的，都需要显式判断叶结点，在叶结点处结束递归。
总结
大部分的二叉树问题都是用递归来解决的。我们解决二叉树类问题时，应遵循的步骤是：
1. 判断问题能否划分问子问题，应当划分为什么样的子问题
2. 判断使用前序遍历还是后序遍历
3. 检查空指针、叶结点等细节
以下是相关题目，这里只列出和本文例题紧密相关的一些题目：
* 简单划分子问题的递归方法：
* 100 - Same Tree[2]
* 101 - Symmetric Tree[3]
* 需要考虑叶结点的题目：
* 111 - Minimum Depth of Binary Tree[4]
* 129 - Sum Root to Leaf Numbers[5]
* 257 - Binary Tree Paths[6]
二叉树是一个有很多套路和技巧的题目类型。这里讨论的只是其中最简单的一类题目，后续还会有更多的关于二叉树类题目的讲解，包括在遍历中使用全局变量、迭代式遍历等。
网友评论