路径和是否等于给定值

路径和是否等于给定值

问题

这个题目说的是，给你一棵二叉树和一个整数，你要判断这棵二叉树上是否存在一条从根到叶子节点的路径，这条路径上所有节点中的数字相加等于给你的整数。

比如说，给你的二叉树是：

    1
  /   \
 2     4
      / \
     8  16

给你的整数是 13。在这棵二叉树中存在一条从根到叶子节点的路径 1->4->8，路径上的数字加起来等于 13，于是要返回 true。

代码

public class AlgoCasts {

  public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
      val = x;
    }
  }

  // Time: O(n), Space: O(n)
  public boolean hasPathSumRecursive(TreeNode root, int sum) {
    if (root == null) return false;
    if (root.left == null && root.right == null) return root.val == sum;
    return hasPathSumRecursive(root.left, sum - root.val) ||
      hasPathSumRecursive(root.right, sum - root.val);
  }

  // Time: O(n), Space: O(n)
  public boolean hasPathSumIterative(TreeNode root, int sum) {
    if (root == null) return false;
    Stack<TreeNode> stack = new Stack<>();
    Stack<Integer> sumStack = new Stack<>();
    stack.push(root);
    sumStack.push(sum);

    while (!stack.isEmpty()) {
      TreeNode n = stack.pop();
      int s = sumStack.pop();
      if (n.left == null && n.right == null && n.val == s) return true;
      if (n.left != null) {
        stack.push(n.left); sumStack.push(s - n.val);
      }
      if (n.right != null) {
        stack.push(n.right); sumStack.push(s - n.val);
      }
    }
    return false;
  }

}