99. Recover Binary Tree

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

Recover the tree without changing its structure.

思路：请看这里

public class Solution {
    TreeNode firstElement = null;
    TreeNode secondElement = null;

    TreeNode prev = new TreeNode(Integer.MIN_VALUE);

    public void recoverTree(TreeNode root){
        traverse(root);

        int temp = firstElement.val;
        firstElement.val = secondElement.val;
        secondElement.val = temp;
    }

    public void traverse(TreeNode root){
        if (root==null)  return;

        traverse(root.left);

        if (firstElement == null && prev.val>=root.val){
            firstElement = prev;
        }

        if (firstElement != null && prev.val>=root.val){
            secondElement = root;
        }
        prev = root;

        traverse(root.right);
    }
}