Java-Iterative-Accepted Solution


  • 0
    R

    I literally did recursive solution first. It was pretty boring. I tried to convert the same recursive to iterative using Stacks. Because in recursive computer has Stack Frames and Stack to keep track of the methods and variables and stuff during the program run.

    public boolean isValidBST(TreeNode root) {
            if( root == null){
                return true;
            }
            Deque<TreeNode> nodeStack = new LinkedList<>();
            Deque<Long> leftMin = new LinkedList<>();
            Deque<Long> rightMax = new LinkedList<>();
            nodeStack.add(root);
            leftMin.add(Long.MIN_VALUE);
            rightMax.add(Long.MAX_VALUE);
    
            while (!nodeStack.isEmpty()){
                TreeNode node = nodeStack.removeFirst();
                Long leftMinValue = leftMin.removeFirst();
                Long rightMaxValue = rightMax.removeFirst();
                if( (leftMinValue != null && (long)node.val <= leftMinValue) || (rightMaxValue!=null && (long)node.val >= rightMaxValue)  ){
                    return false;
                }
                if(node.left!=null){
                    nodeStack.add(node.left);
                    leftMin.add(leftMinValue);
                    rightMax.add((long)node.val);
                }
                if( node.right!=null){
                    nodeStack.add(node.right);
                    leftMin.add((long)node.val);
                    rightMax.add(rightMaxValue);
                }
            }
    
            return true;
        }
    

Log in to reply
 

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