"""
给你二叉搜索树的根节点 root ，该树中的两个节点被错误地交换。请在不改变其结构的情况下，恢复这棵树。

进阶：使用 O(n) 空间复杂度的解法很容易实现。你能想出一个只使用常数空间的解决方案吗？

 

示例 1：


输入：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 使二叉搜索树有效。
 

提示：

树上节点的数目在范围 [2, 1000] 内
-231 <= Node.val <= 231 - 1

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/recover-binary-search-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
"""

# 注释掉的部分是空间复杂度O(N)的做法
# 核心思想是二叉搜索树的中序遍历一定是有序的，所以在这样的序列中寻找异常节点进行节点的值的交换
# 之所以能够做到O(1)的空间复杂度是因为中序遍历可以是隐式地，没有必要保存一整个序列，只要知道遍历的时候每个节点的前一个节点是什么就可以发现异常节点了。

class Solution:
    # def dfs(self, root: TreeNode, q: List[TreeNode]) -> None:
    #     if root.left:
    #         q = self.dfs(root.left, q)
    #     q.append(root)
    #     if root.right:
    #         q = self.dfs(root.right, q)
    #     return q

    # def recoverTree(self, root: TreeNode) -> None:
    #     """
    #     Do not return anything, modify root in-place instead.
    #     """
    #     all_nodes = []
    #     all_nodes = self.dfs(root, [])
    #     abnormal_pos = []
    #     for i in range(len(all_nodes)-1):
    #         if all_nodes[i].val > all_nodes[i+1].val:
    #             abnormal_pos.append(i)

    #     if len(abnormal_pos)==1:
    #         i, j = abnormal_pos[0], abnormal_pos[0]+1
    #         tmp = all_nodes[i].val
    #         all_nodes[i].val = all_nodes[j].val
    #         all_nodes[j].val = tmp
    #     else:
    #         i, j = abnormal_pos[0], abnormal_pos[1]+1
    #         tmp = all_nodes[i].val
    #         all_nodes[i].val = all_nodes[j].val
    #         all_nodes[j].val = tmp

    def dfs(self, root: TreeNode, pre: TreeNode, q: List):
        if root.left:
            q, pre = self.dfs(root.left, pre, q)

        if pre and pre.val > root.val:
            q.append((pre, root))
        pre = root

        if root.right:
            q, pre = self.dfs(root.right, pre, q)
        return q, pre

    def recoverTree(self, root: TreeNode) -> None:
        q, _ = self.dfs(root, None, [])
        if len(q) == 1:
            i, j = q[0][0], q[0][1]
            tmp = i.val
            i.val = j.val
            j.val = tmp
        else:
            i, j = q[0][0], q[1][1]
            tmp = i.val
            i.val = j.val
            j.val = tmp
