[Java] simple O(Height) space and O(n) time solution


  • 0
    B
        public boolean findTarget(TreeNode root, int k) {
            Stack<TreeNode> s1 = new Stack<>();
            Stack<TreeNode> s2 = new Stack<>();
            TreeNode lstNode = root.left;
            TreeNode rstNode = root.right;
            TreeNode left = root.left, right = root.right;
            boolean lstTraversal = true, rstTraversal = true;
    
            s1.push(root);
            s2.push(root);
            
            while(left != right){
                
                //go to min node
                while(lstNode != null && lstTraversal){
                    s1.push(lstNode);
                    lstNode = lstNode.left;
                }
    
                //select min node and move pointer to next node
                if(lstTraversal){
                    lstTraversal = false;
                    left = s1.pop();
                    lstNode = left.right;                
                }
                
                //go to max Node
                while(rstNode != null && rstTraversal){
                    s2.push(rstNode);
                    rstNode = rstNode.right;
                }
                
                //select max and move pointer to next node
                if(rstTraversal){
                    rstTraversal = false;
                    right = s2.pop();
                    rstNode = right.left;                
                }
                
                if(left == right) break;
                if(left.val + right.val == k) return true;
                if(left.val + right.val > k) rstTraversal = true;
                else lstTraversal = true;
            }
            
            return false;
        }
    

Log in to reply
 

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