LeetCode 112 - Path Sum

https://leetcode.com/problems/path-sum/

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.

Note: A leaf is a node with no children.

Example:

Given the below binary tree and sum = 22,

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

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

https://leetcode.com/problems/path-sum/discuss/36378/AcceptedMy-recursive-solution-in-Java
sum: represents the remaining path sum from current node to leaf node before the current node is taken into consideration. That's why for the leaf node, we
need to do sum - root.val ==

The basic idea is to subtract the value of current node from sum until it reaches a leaf node and the subtraction equals 0, then we know that we got a hit. Otherwise the subtraction at the end could not be 0.

The most intuitive way is to use a recursion here. One is going through the tree by considering at each step the node itself and its children. If node is not a leaf, one calls recursively hasPathSum method for its children with a sum decreased by the current node value. If node is a leaf, one checks if the the current sum is zero, i.e if the initial sum was discovered.

• Time complexity : we visit each node exactly once, thus the time complexity is $\mathcal{O}(N)$, where $N$ is the number of nodes.
• Space complexity : in the worst case, the tree is completely unbalanced, e.g. each node has only one child node, the recursion call would occur $N$ times (the height of the tree), therefore the storage to keep the call stack would be $\mathcal{O}(N)$. But in the best case (the tree is completely balanced), the height of the tree would be $\log(N)$. Therefore, the space complexity in this case would be $\mathcal{O}(\log(N))$. 

  public boolean hasPathSum(TreeNode root, int sum) {

    if (root == null)

      return false;

    sum -= root.val;

    if ((root.left == null) && (root.right == null))

      return (sum == 0);

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

  }

X. Stack

  public boolean hasPathSum(TreeNode root, int sum) {

    if (root == null)

      return false;

    LinkedList<TreeNode> node_stack = new LinkedList();

    LinkedList<Integer> sum_stack = new LinkedList();

    node_stack.add(root);

    sum_stack.add(sum - root.val);

    TreeNode node;

    int curr_sum;

    while (!node_stack.isEmpty()) {

      node = node_stack.pollLast();

      curr_sum = sum_stack.pollLast();

      if ((node.right == null) && (node.left == null) && (curr_sum == 0))

        return true;

      if (node.right != null) {

        node_stack.add(node.right);

        sum_stack.add(curr_sum - node.right.val);

      }

      if (node.left != null) {

        node_stack.add(node.left);

        sum_stack.add(curr_sum - node.left.val);

      }

    }

    return false;

  }

X. BFS, level order traversal