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

题目链接

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

题目

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

思路

二叉搜索树的中序遍历就是一个升序数组。

代码

/**
 * @param {TreeNode} root
 * @param {number} k
 * @return {number}
 */
var kthSmallest = function(root, k) {
  const stack = [];
  while(stack.length || root) {
    while(root) {
      stack.push(root);
      root = root.left;
    }
    const node = stack.pop();
    if(--k === 0) {
      return node.val;
    }
    root = node.right;
  }
};

复杂度分析

• 时间复杂度：$O(n)$。
• 空间复杂度：$O(n)$。