一、题目

Given a binary tree and a sum, determine(查明) if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

Example:

Given the below binary tree and sum = 22,

	      5
	     / \
	    4   8
	   /   / \
	  11  13  4
	 /  \      \
	7    2      1

Result： return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.

---

二、分析

【1】常用的递归

设计一个 currSum 记录当前路径的总和。

【1】 判断当前结点是否为叶子结点

• 如果是叶子结点，那么下一步就返回 currSum 是否等于 sum .
• 如果非叶子结点，那么将 sum 的值减去 currSum ，然后递归搜索左子树、右子树。

public class PathSum {
  public static boolean hasPathSum(TreeNode root, int sum) {

    if (root == null)   return false;

    int curr = root.val;
    if (root.right == null && root.left == null)
        return curr == sum;

    return hasPathSum(root.left, sum-curr) || hasPathSum(root.right, sum-curr);
  }
}

---

复杂度分析：

时间复杂度: O(N)

• 每个结点只访问一次，因此时间复杂度为 O(N)，其中 N 是结点的数量。

空间复杂度：O(N) / O(log(N)

• 最坏情况下，整棵树是非平衡的，例如每个节点都只有一个孩子，递归会调用 N 次（树的高度），因此栈的空间开销是 O(N) 。
• 最好情况下，树是完全平衡的，高度只有 log(N)，因此在这种情况下空间复杂度只有 O(log(N)) 。

---

【2】迭代代替递归

【1】定义两个栈 (nodeStack、integerStack) 和一个 curr 计数器，用来记录 sum 减去当前遍历结点的值后的结果。

【2】当正在遍历的结点的左右子结点为空且 curr == 0，证明路径上有组成总和为 sum 的各个结点。

【3】如果上述条件不成立，那么，将其右节点 push 入栈，相当于先遍历右子树。重复上述过程！

public static boolean hasPathSum2(TreeNode root, int sum) {

  Stack<TreeNode> nodeStack = new Stack<>();
  Stack<Integer> integerStack = new Stack<>();

  nodeStack.push(root);
  integerStack.push(sum - root.val);

  TreeNode node;
  int curr;
  while (!nodeStack.isEmpty()) {
      node = nodeStack.pop();
      curr = integerStack.pop();
      if (node.left == null && node.right == null && curr == 0)
          return true;
      if (node.right != null) {
          nodeStack.push(node.right);
          integerStack.push(curr-(node.right.val));
      }
      if (node.left != null) {
          nodeStack.push(node.left);
          integerStack.push(curr-(node.left.val));
      }
  }
  return false;
}

复杂度分析：

时间复杂度: O(N)

• 每个结点只访问一次，因此时间复杂度为 O(N)，其中 N 是结点的数量。

空间复杂度：O(N) / O(log(N)

使用了两个栈，一个用于存储树的结点

• 最坏情况 —> O(N)
• 最好情况 —> O(log(N))，树是平衡的！

---

三、树题总结

这是统一的 main 函数

public static void main(String[] args) {
     TreeNode root = new TreeNode(3);
     root.left = new TreeNode(9);
     root.right = new TreeNode(20);
     root.right.left = new TreeNode(15);
     root.right.right = new TreeNode(7);
     System.out.println(hasPathSum(root, 29));	//false
}

---

其实，做为树的递归题目是非常有套路可循的，因为树有两个分支，所以在递归里也有两个分支，一般是通过 递归 A (|| &&) 递归 B 来实现分支。只要明白了这一点，递归函数就不会很难设计。