题目描述

二叉搜索树中的两个节点被错误地交换。

请在不改变其结构的情况下，恢复这棵树。

示例 1:

输入: [1,3,null,null,2]

   1
  /
 3
  \
   2

输出: [3,1,null,null,2]

   3
  /
 1
  \
   2

示例 2:

输入: [3,1,4,null,null,2]

  3
 / \
1   4
   /
  2

输出: [2,1,4,null,null,3]

  2
 / \
1   4
   /
  3

题解

根据中序遍历是递增的这一性质, 这道题在中序遍历的基础上去做.

只有两个数被交换, 所以找到比上一个节点数值小的节点即可.

如下图所示, 中序遍历顺序是 4,2,3,1,我们只要找到节点4和节点1交换顺序即可!

这里我们有个规律发现这两个节点:

第一个节点,是第一个按照中序遍历时候前一个节点大于后一个节点,我们选取前一个节点,这里指节点4;

第二个节点,是在第一个节点找到之后, 后面出现前一个节点大于后一个节点,我们选择后一个节点,这里指节点1;

只要找到了这两个节点, 交换其数值即可, 不需要动结构.

迭代

public void recoverTree(TreeNode root) {
    Stack<TreeNode> stack = new Stack<>();
    TreeNode firstNode = null;
    TreeNode secondNode = null;
    TreeNode preNode = new TreeNode(Integer.MIN_VALUE);
    TreeNode cur = root;

    while (cur!=null||!stack.isEmpty()){
        while (cur!=null){
            stack.push(cur);
            cur = cur.left;
        }

        cur=stack.pop();
        if (firstNode==null&&cur.val<preNode.val) firstNode = preNode;
        if (firstNode!=null&&cur.val<preNode.val) secondNode = cur;
        preNode = cur;
        cur = cur.right;
    }

    int temp = firstNode.val;
    firstNode.val = secondNode.val;
    secondNode.val = temp;
}

递归

class Solution {
    TreeNode firstNode = null;
    TreeNode secondNode = null;
    TreeNode preNode = new TreeNode(Integer.MIN_VALUE);

    public void recoverTree(TreeNode root) {
        inOrder(root);
        int temp = firstNode.val;
        firstNode.val = secondNode.val;
        secondNode.val = temp;
    }

    private void inOrder(TreeNode root) {
        if (root!=null){
            inOrder(root.left);
            if (firstNode==null&&root.val<preNode.val) firstNode = preNode;
            if (firstNode!=null&&root.val<preNode.val) secondNode = root;
            preNode = root;
            inOrder(root.right);
        }
    }
}