leetcode 99. ツリーの復元

99.リカバリツリーツリーツリーツリーの2つのノードが誤って交換された.
構造を変えずに、この木を復元してください.
例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)空間複雑度を用いた解法は容易に実現できる.定数空間だけを使う解決策を考え出せますか?

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def recoverTree(self, root: TreeNode) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
        res = []
        err = []
        def insort(root):#        
            if not root: return 
            insort(root.left)
            res.append(root.val)
            insort(root.right)

        def change(root):#        
            if not root: return 
            if root.val in err:
                root.val = err[0] if root.val == err[1] else err[1]
            change(root.left)
            change(root.right)

        insort(root)#    ，      
        sorted_res = sorted(res)#        ，           
        for i in range(len(res)):#
            if sorted_res[i] != res[i]:
                err.append(res[i])
        change(root)   #    ，