Non-recursive using two stacks - java


  • 0
    D

    The idea is the following: while popping out a node (and a number) from the stacks subtract the value of the right child (of the node we are popping out) from the number at the top of the stack and push it back to keep track of the sum.

    public boolean hasPathSum(TreeNode root, int sum) {
            if(root==null) return false;
            Stack<TreeNode> nodes = new Stack<TreeNode>();
            Stack<Integer> numbers = new Stack<Integer>();
            nodes.push(root);
            numbers.push(sum - root.val);
            TreeNode node = root;
            
            while(!nodes.isEmpty()){
                if(node.left==null && node.right==null && numbers.peek()==0) return true;
                if(node.left!=null){
                    node=node.left;
                    nodes.push(node);
                    numbers.push(numbers.peek()-node.val);
                }
                else{
                    node=null;
                    while(node==null && !nodes.isEmpty()){
                        node=nodes.pop().right;
                        if(node!=null){
                            int temp= numbers.pop();
                            numbers.push(temp-node.val);
                            nodes.push(node);
                        }
                        else numbers.pop();
                    }
                }
            }
            return false;
        }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.