叉搜索树中第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

链接：

230. 二叉搜索树中第K小的元素 - 力扣（LeetCode） (leetcode-cn.com)

解题思路?

思路一：递归

中序遍历其实是对其进行排序操作，并且是按从小到大的顺序排序，所以输出第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)

空间复杂度： O(H + K)

参考资料：?力扣