zhangdizhangdi

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

题目

LeetCode 中等

给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 个最小元素（从 1 开始计数）。

示例：
输入：root = [3,1,4,null,2], k = 1
输出：1

输入：root = [5,3,6,2,4,null,null,1], k = 3
输出：3

题解

使用中序遍历

方法：递归

递归 O(N) O(N)

ts
function kthSmallest(root: TreeNode | null, k: number): number {
  let res = null

  let inOrderTraverseNode = function (node: TreeNode) {
    if (node !== null && k > 0) {
      console.log('node', node.val, 'k', k)

      inOrderTraverseNode(node.left)

      console.log('---- node', node.val, 'k', k)

      if (--k === 0) {
        res = node.val
        return
      }

      inOrderTraverseNode(node.right)
    }
  }
  inOrderTraverseNode(root)

  return res
}

const tree = new Tree([5, 3, 6, 2, 4, null, null, 1]),
  k = 6

console.log('🌰', kthSmallest(tree.root, k))

方法：迭代

迭代 O(H + k) O(H)

ts
function kthSmallest(root: TreeNode | null, k: number): number {
  const stack = []
  while (root != null || stack.length) {
    console.log('-------------')
    console.log('root', root?.val, 'k', k)
    console.log(stack.map(i => i.val))

    while (root != null) {
      stack.push(root)
      root = root.left

      console.log(stack.map(i => 'left ' + i.val))
    }

    root = stack.pop()
    --k
    if (k === 0) {
      break
    }

    console.log('root pop', root.val)

    root = root.right
  }
  return +root.val
}

const tree = new Tree([5, 3, 6, 2, 4, null, null, 1]),
  k = 6

console.log('🌰', kthSmallest(tree.root, k))