Simple Solution Using Java


  • 0
    H

    The main idea is that we print a valid BST in order, it would be an increasing list. In this problem, two elements are swapped so the list would not be increasing. There would be at most two peaks. So we try to find the two peaks and devise the value of the two misplaced nodes. Here is the Java code.

    /**
     * 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) {
            if(root == null) return;
            Stack<TreeNode> stack = new Stack<>();
            TreeNode cur = root;
            while(cur != null){
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode last = null;
            TreeNode peak1 = null, valley1 = null, peak2 = null, valley2 = null;
            while(!stack.isEmpty()){
                cur = stack.pop();
                if(cur.right != null){
                    TreeNode r = cur.right;
                    while(r != null){
                        stack.push(r);
                        r = r.left;
                    }
                }
                if(last != null && cur.val < last.val){
                    if(peak1 == null){
                        peak1 = last;
                        valley1 = cur;
                    }else{
                        peak2 = last;
                        valley2 = cur;
                        break;
                    }
                }
                last = cur;
            }
            if(peak2 == null){
                // the swap two are adjacent
                int val = peak1.val;
                peak1.val = valley1.val;
                valley1.val = val;
            }else{
                int val = peak1.val;
                peak1.val = valley2.val;
                valley2.val = val;
            }
        }
    }

Log in to reply
 

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