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

题目描述：

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

示例 1： 

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

 输出：1

 示例 2：

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

输出：3

解题思路 

先来了解下二叉搜索树 二叉搜索树具有如下性质：

• 结点的左子树只包含小于当前结点的数。
• 结点的右子树只包含大于当前结点的数。
• 所有左子树和右子树自身必须也是二叉搜索树。

思路一：递归

中序遍历其实是对其进行排序操作，并且是按从小到大的顺序排序，所以输出第k个即可

/**
 * @param {TreeNode} root
 * @param {number} k
 * @return {number}
 */
var kthSmallest = function(root, k) {
    let res = null;
    let inOrderTraverseNode = function (node) {
        if (node !== null && k > 0) {
            // 先遍历左子树
            inOrderTraverseNode(node.left);
            // 
            if (--k === 0) {
                res = node.val;
                return;
            }
            inOrderTraverseNode(node.right);
        }
    }
    inOrderTraverseNode(root);
    return res;
};

时间复杂度： O(K)

空间复杂度： O(1)，不考虑递归栈所占用的空间，空间复杂度为O(1)

思路二：迭代

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

时间复杂度： O(H + K), H是树的高度， 先到达叶子位置（最小节点位置），复杂度为 O(H)，然后找到第 K 小的元素，复杂度为 O(K)。整体复杂度为 O(H + K)

空间复杂度： O(H)， 栈中最多需要存储 H 个元素

参考资料

二叉搜索树中第K小的元素 - 二叉搜索树中第K小的元素 - 力扣（LeetCode）