112. 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.
For 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.

Solution1：递归pre-order dfs来downwards累积

Time Complexity: O(N) Space Complexity: O(N) 递归缓存

Solution2：Interative stack pre-order dfs，并downwards累积

累积的方式a: 将cur_sum更新到node的值中，share stack
累积的方式b: 若node的值不可变，可再建一个cur_sum的stack；或组pair共存
Time Complexity: O(N) Space Complexity: O(N)

Solution3：Interative stack 法二, 纪录sum & step back

则不用存sum进stack
Time Complexity: O(N) Space Complexity: O(N)

Solution1 Code：

class Solution {
    public boolean hasPathSum(TreeNode root, int sum) {
        if(root == null) return false;
        
        if(root.left == null && root.right == null && root.val == sum) return true;
        
        return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
    }
}

Solution2a Code：

class Solution2a {
    public boolean hasPathSum(TreeNode root, int sum) {
        if(root == null) return false;
        Stack<TreeNode> stack = new Stack<>();
            
        stack.push(root);
        while(!stack.isEmpty()) {
            TreeNode cur = stack.pop();
            if(cur.left == null && cur.right == null && cur.val == sum) return true;
                
            if(cur.right != null) {
                cur.right.val += cur.val;
                stack.push(cur.right);
            }
                    
            if(cur.left != null) {
                cur.left.val += cur.val;
                stack.push(cur.left);
            }
        }
        return false;
    }
}

Solution2b Code：

class Solution2b {
    public boolean hasPathSum(TreeNode root, int sum) {
        if(root == null) return false;
        Stack<TreeNode> stack = new Stack<>();
        Stack<Integer> stack_sum = new Stack<>();
            
        stack.push(root);
        stack_sum.push(root.val);
        while(!stack.isEmpty()) {
            TreeNode cur = stack.pop();
            int cur_sum = stack_sum.pop();
            if(cur.left == null && cur.right == null && cur_sum == sum) return true;
                
            if(cur.right != null) {
                stack.push(cur.right);
                stack_sum.push(cur_sum + cur.right.val);
            }
                    
            if(cur.left != null) {
                stack.push(cur.left);
                stack_sum.push(cur_sum + cur.left.val);
            }
        }
        return false;
    }
}

Solution3 Code：

class Solution3 {
    public boolean hasPathSum(TreeNode root, int sum) {
        // Deque<TreeNode> stack = new ArrayDeque<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while(!stack.isEmpty() || cur != null) {
            while(cur != null) {
                stack.push(cur);
                
                // process
                sum -= cur.val;
                if(cur.left == null && cur.right == null && sum == 0) return true;
                
                cur = cur.left;
            } 
            
            // pop and sum_step_back togeter, but
            // only do that after finishing processing its right_siblings,
            // otherwise when visiting right_siblings, its root will be wrongly sum_step_back.
            while (!stack.isEmpty() && stack.peek().right == cur) {
                cur = stack.pop();
                sum += cur.val;  // sum: step back
            }
            cur = stack.isEmpty() ? null : stack.peek().right;
        }
        return false;
    }
}