恢复完全二叉树（leetcode_99）

给你二叉搜索树的根节点

，该树中的两个节点被错误地交换。请在不改变其结构的情况下，恢复这棵树。

输入：root = [1,3,null,null,2]
输出：[3,1,null,null,2]
解释：3 不能是 1 左孩子，因为 3 > 1 。交换 1 和 3 使二叉搜索树有效。
示例 2：

输入：root = [3,1,4,null,null,2]
输出：[2,1,4,null,null,3]
解释：2 不能在 3 的右子树中，因为 2 < 3 。交换 2 和 3 使二叉搜索树有效。

这里提到完全二叉树就应该想到中序遍历，因为完全二叉树中序遍历的结果就是一个递增数组，按道理来说，最简单的方式就是先把二叉树遍历一遍，得到每个节点组成的数组，然后直接通过数组找到两个错位的节点并交换值。

但是我们也可以发现，不需要专门用个数组来存遍历后的结果，我们只要比较每两个相邻的值看是否符合条件，最多找到两次逆序就可以判断出是否找到需要交换的节点。因此我们需要一个pre指针指向上一次遍历的结果，对于中序遍历来说，就是左子树最右下节点，对于右子树来说，就是当前跟节点，root节点就是最左下节点。

我们这里选择迭代法遍历二叉树。

class Solution

{

public:

    void recoverTree(TreeNode *root)

    {

        stack<TreeNode* > stk;

        TreeNode *x = nullptr;

        TreeNode *y = nullptr;

        TreeNode *pre = nullptr;



        while(root != nullptr || !stk.empty())

        {

            while(root != nullptr)

            {

                stk.push(root);

                root = root->left;

            }



            root = stk.top();

            stk.pop();



            if(pre != nullptr && root->val < pre->val)

            {

                y = root;

                if (x == nullptr)

                {

                    x = pre;

                }

                else

                    break;

            }



            pre = root;

            root = root->right;

        }



        swap(x->val, y->val);

    }

};

条件限定只有一对出现错位，所以只要出现两次逆序就是找到了两个需要交换的节点，比如 1 2 3 7 5 6 4

7

/ \

2 6

/\ /\

1 3 5 4

为什么前一次7和5比较要选择7，后一次4和6比较要选择4，还是那个原因，只有一对错位，若将选5，将5换到后面，则必定出现5 < 6但是在6后面，又引入了新的逆序，同理选6，将6换到前面，则出现6 > 5但是在5的前面

简单来说前面要选最大的，后面要选最小的

class Solution:

    def recoverTree(self, root: TreeNode) -> None:

        x = None

        y = None

        pre = None

        stk = []



        while stk or root:

            while root:

                stk.append(root)

                root = root.left



            root = stk.pop()



            if pre and pre.val > root.val:

                y = root

                if not x:

                    x = pre

                else:

                    break



            pre = root

            root = root.right

        

        x.val, y.val = y.val, x.val

class Solution {

    public void recoverTree(TreeNode root) {

        Deque<TreeNode> stk = new ArrayDeque<>();

        TreeNode pre = null;

        TreeNode x = null;

        TreeNode y = null;



        while (!stk.isEmpty() || root != null) {

            while (root != null) {

                stk.push(root);

                root = root.left;

            }



            root = stk.pop();



            if (pre != null && root.val < pre.val) {

                y = root;

                if (x == null) {

                    x = pre;

                } else {

                    break;

                }

            }



            pre = root;

            root = root.right;

        }



        int tmp = x.val;

        x.val = y.val;

        y.val = tmp;

    }

}