三、二叉树递归框架-子问题划分

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]

二叉树是一个有很多套路和技巧的题目类型。这里讨论的只是其中最简单的一类题目，后续还会有更多的关于二叉树类题目的讲解，包括在遍历中使用全局变量、迭代式遍历等。