恢复二叉搜索树

Tips

题目类型: Tree, BST

题目

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

提示:

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

示例

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

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

题解

1. 由于是 BST, 所以使用中序遍历, 把所有节点存储到 list 中
2. 遍历这个列表 list, 由于 BST 的中序遍历应当是从小到大排列的, 所以如果前面的 val 大于了后面的 val, 说明后面这个应当靠前.
3. 找到两个需要交换的, 交换他们的值即可

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {void} Do not return anything, modify root in-place instead.
 */
var recoverTree = function (root) {
  const list = []
  inOrder(root, list)
  let x = null
  let y = null

  for (let i = 0; i < list.length - 1; i++) {
    if (list[i].val > list[i + 1].val) {
      y = list[i + 1]
      if (!x) x = list[i]
    }
  }

  if (x && y) {
    const tmp = x.val
    x.val = y.val
    y.val = tmp
  }
}

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {TreeNode[]} list
 * @return {void} Do not return anything, modify root in-place instead.
 */
var inOrder = function (root, list) {
  if (!root) return null

  inOrder(root.left, list)
  list.push(root)
  inOrder(root.right, list)
}