99-恢复二叉搜索树

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

---

示例

示例 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

进阶:

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

---

解法

核心思想：两次利用中序遍历该树，第一次遍历为扫描结点值，第二次遍历为把排序后的结点值依次填入。

注意：取排序后的列表值，不能使用pop()

class Solution:
    def recoverTree(self, root: TreeNode) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
        tree = []
        def helper(root,flag):
            if not root:
                return
            helper(root.left,flag)
            if flag=="traverse":
                tree.append(root.val)
            elif flag == "modify":
                # 注意:这里不能使用pop()
                # 排序不会改变pop的顺序
                root.val = tree[0]
                del tree[0]
            helper(root.right, flag)
        # 先遍历
        helper(root, flag="traverse")
        # 排序
        tree.sort()
        # 再替换
        helper(root, flag="modify")

---

相关信息

LeetCode：Discussion | Solution