Thursday, November 6, 2014

Facebook: Print the sum of all the numbers at every vertical level in a binary tree

Print the sum of all the numbers at every vertical level in a binary tree
Idea is similar to the question above.
Recursive solution:
public class Solution {
    public void pathSum(TreeNode root) {
        if (root == null) {
            return;
        }
        
        pathSumHelper(root, 0);
    }
    
    private void pathSumHelper(TreeNode root, int curSum) {
        if (root == null) {
            return;
        }
        
        curSum += root.val;
        
        if (root.left == null && root.right == null) {
            System.out.println(curSum);
            return;
        }
        
        pathSumHelper(root.left, curSum);
        pathSumHelper(root.right, curSum);
    }
}

Iterative Solution:
public class Solution {
    public void pathSum(TreeNode root) {
        if (root == null) {
            return;
        }
        
        Stack<TreeNode> nodeStack = new Stack<TreeNode>();
        Stack<Integer> sumStack = new Stack<Integer>();
        
        nodeStack.push(root);
        sumStack.push(root.val);
        
        while (!nodeStack.isEmpty()) {
            TreeNode curr = nodeStack.pop();
            int curSum = sumStack.pop();
            
            if (curr.left == null && curr.right == null) {
                System.out.println(curSum);
                continue;
            }
            
            if (curr.right != null) {
                nodeStack.push(curr.right);
                sumStack.push(curSum + curr.right.val);
            }
            
            if (curr.left != null) {
                nodeStack.push(curr.left);
                sumStack.push(curSum + curr.left.val);
            }
        }
    }
}

No comments:

Post a Comment