99_恢复二叉搜索树

类型：树

• 99. 恢复二叉搜索树 ❤️

  https://leetcode-cn.com/problems/recover-binary-search-tree/

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

  💡 中序遍历

  正常搜索树中序遍历的结果是升序的。我们可以通过中序遍历，得到该树结点值的中序遍历数组 inorderArr，同时我们也在遍历过程中，直接把结点地址存入一个数组 inorderNodes，方便我们后续修改。

  我们找出 inorderArr 中不符合升序的元素的下标，直接通过 inorderNodes 访问对应结点，修改其值即可。

  class Solution:
      def recoverTree(self, root: TreeNode) -> None:
          """
          Do not return anything, modify root in-place instead.
          """
  
          inorderNodes = []
          inorderArr = []
  
          def inorderTraverse(node):
              if not node:
                  return
              inorderTraverse(node.left)
              inorderNodes.append(node)
              inorderArr.append(node.val)
              inorderTraverse(node.right)
  
          inorderTraverse(root)
          sortedArr = inorderArr[:]
          sortedArr.sort()
  
          # 通过中序遍历的队列与有序队列比较，找出错位的结点
          disNodes = []
          for i in range(len(inorderArr)):
              if inorderArr[i] != sortedArr[i]:
                  disNodes.append(inorderNodes[i])
  
          disNodes[0].val, disNodes[1].val = disNodes[1].val, disNodes[0].val

  时间复杂度：O(n)，空间复杂度：O(n)