LeetCode 例题精讲 | 02 Path Sum：二叉树的子问题划分
本期例题：LeetCode 112 - Path Sum[1]（Easy）
给定一个二叉树和一个目标和，判断该树中是否存在根结点到叶结点的路径，这条路径上所有结点值相加等于目标和。返回 true 或者 false。
示例：
给定如下二叉树，以及目标和 sum = 22。以下二叉树存在路径 5->4->11->2 满足目标和。
题目示例
链表和二叉树是大家面试中最常遇到的两种数据结构。上一期我们讲了链表的遍历框架，这一期我们接着讲二叉树的遍历框架。二叉树的题目比链表更常见、变种更多，但是掌握了基本思想则一点不难。
说到二叉树的遍历框架，很多人的脑海里立马蹦出来的就是前序、中序和后序遍历。但是机械地记住前中后序遍历没有太大意义，我们首先要掌握的是二叉树的递归思想。究竟怎样递归才能快速地解决二叉树问题呢？
这篇文章将会包含：
二叉树的递归结构 二叉树问题的子问题划分 本期例题：Path Sum 的解法 相关题目
二叉树与递归
如何定义二叉树？二叉树是每个结点最多只有两个分支的树。这是一个正确的定义，但对解决问题没有帮助。我们需要的是二叉树的递归定义：
空树是一个二叉树 如果 和 是二叉树，那么用一个根结点连接 和 得到的也是二叉树
可以看到，二叉树天生就是递归的。遍历一个二叉树，先处理根结点，左右两个子树又是二叉树，可以递归处理。这便是递归前序遍历的原理。
我们很早就学会了递归函数，觉得它太简单，经常会忘记它的意义。递归本质上是将问题分解成同类的子问题，反复调用自己来进行求解。你可能更熟悉动态规划里的子问题，但实际上任何有递归函数的地方都有子问题。
许多二叉树问题都可以通过划分子问题来求解。如果我们思考出了子问题的划分方式，那么使用何种方式进行递归遍历，都是能很容易就推导出的。
下面，我们就用今天的例题 Path Sum （路径和）来学习子问题的划分方式。
Path Sum 的子问题划分
我们都知道，递归有两大要点：
反复调用自身 终止条件
而在二叉树结构上进行递归，则这两大要点变为：
递归调用自己两个子树 在叶结点处终止递归
其中，调用子树的部分是重点。我们需要保证在子树上求解的是与原问题相同的子问题，才能递归调用自身。而终止条件可以放在最后作为细节考虑。
再看这道 Path Sum 问题，我们的目标是找到从根到叶的路径，和为 22。如果左右某个子树中存在一个从根到叶的路径和为 17，再连上根结点的 5，正好是 17 + 5 = 22。我们把整个的 sum = 22 的问题变成了两个子树上的 sum = 17 问题，就可以对自身递归调用。
Path Sum 问题有多个变种，难度各有不同。本例题中只关注从根到叶的路径，是最简单的一种情况，直接使用最直观的递归方式即可。
根据以上的基本思路，我们可以得到以下的递归代码：
boolean hasPathSum(TreeNode root, int sum) {
int target = sum - root.val;
return hasPathSum(root.left, target)
|| hasPathSum(root.right, target);
}
这里的代码显然不完整，我们还要考虑递归终止情况的处理，以及一些边界情况。下面会讨论关于空指针、叶结点的几个细节问题。
递归解法的细节问题
细节 1：root == null 表示什么
void processTree(TreeNode root) {
if (root == null) {
// 空树
}
}
在二叉树中， root 为 null 表示空树。但这里的空树有两种含义：
第一个含义是整棵树都为空。二叉树题目一般都需要考虑这种情况，否则面试官会认为你考虑边界情况不周全。
第二个含义是某个子树为空。由于函数是递归调用的，参数 root 可以表示任何一个子树。特别的，叶结点的两个子树都为空，递归到这里就会自然遇到两个 root == null 的情况（如下图的 3、4）。一般情况下，我们用 root == null 作为递归的终止条件。
在例题 Path Sum 中，我们可以在 root == null 时判断目标和是否已经满足，即 sum 减为 0：
boolean hasPathSum(TreeNode root, int sum) {
if (root == null) {
return sum == 0;
}
int target = sum - root.val;
return hasPathSum(root.left, target)
|| hasPathSum(root.right, target);
}
细节 2：是否要判断叶结点
然而，上面的代码在 LeetCode 中提交会得到 Wrong Answer。当树为空树、sum = 0 时，我们的代码会错误地返回 true！
错误的原因是我们的递归终止条件写得太想当然了。符合条件的路径会把 sum 减为 0，但 sum 为 0 不代表找到了符合条件的路径。
再回顾题目描述：
给定一个二叉树和一个目标和，判断该树中是否存在根结点到叶结点的路径，这条路径上所有结点值相加等于目标和。
我们应当在叶结点处进行判断并结束递归，而不是在叶结点的两个空子树处判断。
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);
}
一个小经验是：凡是题目描述里提到叶结点的，都需要显式判断叶结点，在叶结点处结束递归。
总结
大部分的二叉树问题都是用递归来解决的。我们解决二叉树类问题时，应遵循的步骤是：
判断问题能否划分问子问题，应当划分为什么样的子问题 判断使用前序遍历还是后序遍历 检查空指针、叶结点等细节
以下是相关题目，这里只列出和本文例题紧密相关的一些题目：
简单划分子问题的递归方法： 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]
二叉树是一个有很多套路和技巧的题目类型。这里讨论的只是其中最简单的一类题目，后续还会有更多的关于二叉树类题目的讲解，包括在遍历中使用全局变量、迭代式遍历等，敬请期待。
参考资料
LeetCode 112 - Path Sum: https://leetcode.com/problems/path-sum/
[2]100 - Same Tree: https://leetcode.com/problems/same-tree
[3]101 - Symmetric Tree: https://leetcode.com/problems/symmetric-tree
[4]111 - Minimum Depth of Binary Tree: https://leetcode.com/problems/minimum-depth-of-binary-tree
[5]129 - Sum Root to Leaf Numbers: https://leetcode.com/problems/sum-root-to-leaf-numbers/
[6]257 - Binary Tree Paths: https://leetcode.com/problems/binary-tree-paths/