Binary Search Tree Kth Smallest Element

思路

对于一个 BST 来说：

左子树所有节点值 < 当前节点值
右子树所有节点值 > 当前节点值

因此，对 BST 进行中序遍历（左 -> 根 -> 右），得到的序列一定是严格升序排列的。

算法步骤

定义一个全局 counter 记录访问的节点数量
每次访问一个节点时 counter++
当 counter === k 时，记录当前节点值
递归左 → 根 → 右
找到了就停止进一步遍历

时间复杂度： $O(h + k)$

空间复杂度： $O(h)$

代码

迭代

function kthSmallest(root: TreeNode | null, k: number): number {
  const stack: TreeNode[] = [];
  let current: TreeNode | null = root;
  let count = 0;

  while (current !== null || stack.length > 0) {
    // 一直向左走
    while (current !== null) {
      stack.push(current);
      current = current.left;
    }

    // 处理当前最小节点
    current = stack.pop()!;
    count++;

    if (count === k) {
      return current.val;
    }

    // 转向右子树
    current = current.right;
  }

  throw new Error("k is out of range");
}

递归

function kthSmallest(root: TreeNode | null, k: number): number {
  let result = -1;
  let count = 0;

  function inorder(node: TreeNode | null) {
    if (!node || result !== -1) return;

    inorder(node.left);

    count++;
    if (count === k) {
      result = node.val;
      return;
    }

    inorder(node.right);
  }

  inorder(root);
  return result;
}

Binary Search Tree Kth Smallest Element

思路

算法步骤

代码

迭代

递归

目录