Java iterative solution with one stack


  • 0
    public boolean hasPathSum(TreeNode root, int sum) {
            Stack<TreeNode> visitedNodes = new Stack<>();
            TreeNode prev = null;
           
            while(root!=null || !visitedNodes.isEmpty()){
                while(root!=null){
                    visitedNodes.push(root);
                    sum -= root.val;
                    prev = root;
                    root = root.left;
                }
                root = visitedNodes.peek();
                if(root.left==null && root.right == null && sum==0) return true;
                if(root.right != null && root.right != prev){
                    root = root.right;
                }else{
                    sum += root.val;
                    prev = visitedNodes.pop();
                    root = null;
                }
            }
            
            return false;
        }
    
    

Log in to reply
 

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