Java O(1) space inorder Traversal


  • 0
    S
    public class Solution {
        
        private TreeNode[] queue = new TreeNode[3];
        private TreeNode[] mistake =  new TreeNode[3];
        private int count = -1;
        
        public void recoverTree(TreeNode root) {
            if(root == null){
                return;
            }
            inOrder(root);
            int value ;
            if(count >= 2 && queue[(count- 1) % 3].val > queue[count % 3].val ){
                mistake[1] =  queue[count % 3];
            }
            else if(count == 1 &&  queue[0].val > queue[1].val ){
                mistake[1] = queue[1];
            }
            value = mistake[0].val;
            mistake[0].val = mistake[1].val;
            mistake[1].val = value;
    
        }
    
        private void inOrder(TreeNode root){
            if(root != null){
                if(root.left != null){
                    inOrder(root.left);
                }
                count++;
                queue[count % 3] = root;
                if(count == 1 &&  queue[0].val >  queue[1].val){
                        mistake[0] = queue[0];
                    }
                if(count >= 2 && (queue[(count-2)%3].val > queue[(count-1)%3].val && queue[(count-1)%3].val < queue[count%3].val || queue[(count-2)%3].val < queue[(count-1)%3].val && queue[(count-1)%3].val > queue[count%3].val)){
                    if(mistake[0] == null){
                        mistake[0] =  queue[(count-1)%3];
                    }
                    else {
                        mistake[1] =  queue[(count-1)%3];
                    }
                }
                if(root.right != null){
                    inOrder(root.right);
                }
            }
        }
    }
    

Log in to reply
 

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