My result based on a (sort of ) iterator


  • 0
    T

    I used the basic code from the last question , "validate binary search tree", which gives me a sort of iterator. then basically you find the first "kink", and that it is the first node to be swapped, its true location is before the first node bigger than it. once u find these 2, just swap.

        /**
     * Definition for binary tree
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    
    
    
    /**
     * Definition for binary tree
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
     
     class Pair {
         
         public TreeNode tr;
         public boolean secondTime;
         
         public Pair(TreeNode tr) {this.tr = tr; secondTime = false;}
     }
    public class Solution {
        TreeNode last ;
        TreeNode begin;
        TreeNode end;
        boolean initialized = false;
    
            public void recoverTree(TreeNode root) {
    
            if (root == null) return ;
            Stack<Pair> st = new Stack<Pair>();
            st.push(new Pair(root));
            while(! st.empty()) {
                Pair pair = st.pop();
                if (pair.tr == null) continue;
                
                if (pair.secondTime) {
                    // visit
                    if (last!=null && begin == null && last.val  >= pair.tr.val) {
                        begin = last;
                    }
                    if (begin != null && begin.val < pair.tr.val) {
                        end = last;
                        swap(begin, end);
                        return;
                    }
                    last = pair.tr;
                    initialized = true;
                    if (pair.tr.right != null)
                    st.push(new Pair(pair.tr.right));
                } else {
                    pair.secondTime = true;
                    st.push(pair);
                    if (pair.tr.left != null)
                    st.push(new Pair(pair.tr.left));
                }
            }
            
            swap(begin,last);
            return ;
        }
        
        
        void swap(TreeNode a , TreeNode b ) {
            int tmp = a.val;
            a.val = b.val;
            b.val = tmp;
        }
    }

Log in to reply
 

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