二叉树的路径和。
解题“七步走” (保持这种sense)：
- 题意 Scenario
- 假设 Assumptions
- 举例与输入输出 Examples and figure out Input/Output
- 思路（什么数据结构， 什么算法）Thinking Process (What data structure, algorithm?)
- 代码 Coding
- 复杂度分析 Complexity Analysis
- 测试 Tests
题目要求
原题链接
在给定的一个二叉树中，从全局的根节点开始，假若能找到一条到叶子的路径，使得路径上的所有点的和等于给定的数值，返回真；反之，返回假。
假设
面试者：给定的二叉树的值，可以有负数吗？
面试官：本题是否有节点为负数对本题没有影响。
举例与输入输出
例子直接用LeetCode上的图，还是很好理解的。
在本例子中，给定的和为22，由根节点5开始，顺着5 -> 4 -> 11 -> 2 (2为叶子节点)形成的路径，可以满足和为22的要求。
思路1: 正向思维
我们从自底向上的postorder traversal（后序遍历）的思路，通过找每一片叶子，回溯向上看看能否形成和为target值的路径。
这个方法的难点在于：
二叉树的起始位置是它的全局的根，如果要走到叶子节点，首先就需要递归到叶子节点，而后从底向上一直走到根节点看这条分支是否成立，不成立的话又要继续看从下一个叶子节点开始看的那一条分支。该方法开销大。
思路2: 逆向思维
想想，我们是否有可能延续前面几期的内容，通过类似前序遍历的分治方法，达到目的呢？
答案是可以的。因为，假如一条路径满足从叶子开始往回走到根和为目标值，其实也就意味着从根开始，目标值逐渐地减去当前节点值，一直减到最后的叶节点的时候，目标值就减到0了。
其实，这就是用了我们小学就学到的知识：减法是加法的逆运算。
这样一来，我们就在分治的每一步“分”（Divide）的时候，把(target - 当前节点的值)带到下一个子步骤中去。
至于分治法的base cases, 我们就是要判断何时定真假：其实就是到了叶子节点，假如当前值减去叶子节点可以得到0，即为真，反之为假。
代码
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean hasPathSum(TreeNode root, int sum) {
// Base case 1: 已经走到叶子节点之下的null节点，发现叶子节点的值无法等于当前目标值
if (root == null) {
return false;
}
// Base case 2: 在叶子节点时叶子节点的值能等于当前目标值
else if (root.left == null && root.right == null && root.val == sum) {
return true;
}
boolean left = hasPathSum(root.left, sum - root.val);
boolean right = hasPathSum(root.right, sum - root.val);
return left || right;
}
}
时间空间复杂度
时间复杂度：遍历整个树的节点，所以是O(n)。
空间复杂度：为递归栈的深度，所以是O(log(n))。