Recover Binary Search Tree(Hard)

LeetCode Source

Two elements of a binary search tree (BST) are swapped by mistake.

Recover the tree without changing its structure.

解法1：We can use in-order traverse to find the swapped element. During the traverse, we can find the element that is smaller than the previous node. Using this method we can find the swapped node. Save it and swap them. Done.

The time complexity is O(n). But the space complexity is not constant, since we use recursive function.

public class Solution {
    TreeNode node1 = null;
    TreeNode node2 = null;
    public void recoverTree(TreeNode root) {
        inorderTraverse(root);
        int tmp = node1.val;
        node1.val = node2.val;
        node2.val = tmp;
    }

    TreeNode prev = null;
    private void inorderTraverse(TreeNode root) {
        if (root == null)
            return;
        inorderTraverse(root.left);
        if (prev != null) {
            if (root.val <= prev.val) {
                if (node1 == null) 
                    node1 = prev;
                node2 = root;
            }
        }
        prev = root;
        inorderTraverse(root.right);
    }
}

解法2:Morris traverse

References:

1 Recover Binary Search Tree from lifeincode

2 Morris Traversal方法遍历二叉树