【数据结构】二叉搜索树

[miracles1919]

参考：东哥带你刷二叉搜索树（特性篇）

BST 的特性

• 对于每一个节点，左子树的节点都比当前节点小，右子树的节点都比当前节点大
• 对于每一个节点，左子树和右子树都是 BST

BST 的中序遍历是有序的（升序）

模板

function BST(root, target) {
  if (root.val === target) {
    // ...
  } else if (root.val < target) {
    BST(root.right, target)
  } else if (root.val > target) {
    BST(root.left, target)
  }
}

[miracles1919]

230. 二叉搜索树中第K小的元素

var kthSmallest = function (root, k) {
    let i = 0
    let res = 0

    function traverse(root) {
        if (root === null) return
        traverse(root.left)
        i++
        if (i === k) {
            res = root.val
            return
        }
        traverse(root.right)
    }

    traverse(root)
    return res
};

[miracles1919]

538. 把二叉搜索树转换为累加树

var convertBST = function (root) {
    let sum = 0
    function traverse(root) {
        if (root === null) return

        // 先遍历右子树
        traverse(root.right)
        sum += root.val
        root.val = sum
        traverse(root.left)
    }
    traverse(root)
    return root
};

[miracles1919]

700. 二叉搜索树中的搜索

var searchBST = function (root, val) {
    if (root === null) return null

    if (root.val > val) {
        return searchBST(root.left, val)
    }

    if (root.val < val) {
        return searchBST(root.right, val)
    }

    return root
};

[miracles1919]

98. 验证二叉搜索树

var isValidBST = function (root) {
    return traverse(root, null, null)
};

function traverse(root, min, max) {
    if (root === null) return true

    if (min !== null && min >= root.val) return false

    if (max !== null && max <= root.val) return false

    return traverse(root.left, min, root.val) && traverse(root.right, root.val, max)
}

[miracles1919]

701. 二叉搜索树中的插入操作

var insertIntoBST = function (root, val) {
    if (root === null) return new TreeNode(val)

    if (root.val > val) {
        root.left = insertIntoBST(root.left, val)
    } else if (root.val < val) {
        root.right = insertIntoBST(root.right, val)
    }

    return root
};

[miracles1919]

450. 删除二叉搜索树中的节点

找到目标节点后

• 如果是末端节点（存在0、1个子节点），直接删除
• 如果不是末端节点（存在2个子节点）
  • 获取目标节点右子树的最小节点（或者左子树的最大节点）
  • 将目标节点替换成最小节点

var deleteNode = function (root, key) {
    if (root === null) return null
    if (root.val === key) {
        // 末端节点
        if (root.left === null) return root.right
        if (root.right === null)  return root.left

        // 两个子节点
        // 右子树最小节点
        const rightMinNode = getMinNode(root.right)
        // 删除右子树最小节点
        root.right = deleteNode(root.right, rightMinNode.val)
        // 当前节点替换成最小节点
        rightMinNode.left = root.left
        rightMinNode.right = root.right
        root = rightMinNode

    } else if (root.val > key) {
        root.left = deleteNode(root.left, key)
    } else if (root.val < key) {
        root.right = deleteNode(root.right, key)
    }

    return root
};

function getMinNode(node) {
    // BST最左边就是最小的
    while (node.left !== null) {
        node = node.left
    }
    return node
}

[miracles1919]

剑指 Offer II 054. 所有大于等于节点的值之和 1038. 从二叉搜索树到更大和树

反序中序遍历

var bstToGst = function(root) {
  let sum = 0
  function bfs (root) {
    if (root === null) return 
    bfs(root.right)
    sum += root.val
    root.val = sum
    bfs(root.left)
  }
  bfs(root)
  return root
};

[miracles1919]

96. 不同的二叉搜索树

var numTrees = function (n) {
  // 定义 [lo, hi] 能组成 count(lo,hi) 种二叉树
  function count(lo, hi) {
    if (lo > hi) return 1
    let res = 0
    for (let i = lo; i <= hi; i++) {
      const left = count(lo, i - 1)
      const right = count (i + 1, hi)
      res += left * right
    }
    return res
  }
  return count(1, n)
}

优化

var numTrees = function (n) {
  const map = new Map()
  function count(lo, hi) {
    if (lo > hi) return 1
    let res = 0
    const key = `${lo}${hi}`
    if (map.get(key)) return map.get(key)

    for (let i = lo; i <= hi; i++) {
      const left = count(lo, i - 1)
      const right = count (i + 1, hi)
      res += left * right
    }
    map.set(key, res)
    return res
  }
  return count(1, n)
}

[miracles1919]

95. 不同的二叉搜索树 II

var generateTrees = function (n) {
  function createTrees (lo, hi) {
    let res = []
    if (lo > hi) {
      res.push(null)
      return res
    }
    for (let i = lo; i <= hi; i++) {
      const leftTrees = createTrees(lo, i - 1)
      const rightTrees = createTrees(i + 1,  hi)
      leftTrees.forEach(leftNode => {
        rightTrees.forEach(rightNode => {
          const node = new TreeNode(i, leftNode, rightNode)
          res.push(node)
        })
      })
    }
    return res
  }

  return createTrees(1, n)
}