Iterative In-order traversal, Java solution.


  • 0

    used iterative in-order traversal. find the reverse pairs.

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    public class Solution {
        public void recoverTree(TreeNode root) {
            TreeNode[] dup = new TreeNode[2];
            Stack<TreeNode> s = new Stack<TreeNode>();
            TreeNode prev = null;
            TreeNode curr = root;
            while(!s.empty() || curr != null){
                if(curr==null) {
                    curr = s.pop();
                    
                    //record the reversed pair.
                    if(prev != null && curr.val < prev.val) {
                        if(dup[0] == null) {
                            dup[0] = prev;
                        }                        
                        dup[1] = curr;
                    }
                    
                    prev = curr;
                    curr = curr.right;
                } else {
                    s.push(curr);
                    curr = curr.left;
                }
            }
            
            int temp = dup[0].val;
            dup[0].val = dup[1].val;
            dup[1].val = temp;
        }
    }
    
    

Log in to reply
 

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