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

思路&js代码

1、中序遍历

写法1：好理解一点

var kthSmallest = function (root, k) {
    const list = []
 
    const dfs = (root) => {
        if (root === null || list.length >= k) return
 
        dfs(root.left)
        list.push(root)
        dfs(root.right)
    }
    dfs(root)
 
    return list[k - 1].val
};

var kthSmallest = function(root, k) {
    let ans = 0;
    function dfs(node) {
        if (node === null || k === 0) {
            return;
        }
        dfs(node.left); // 左
        if (--k === 0) {
            ans = node.val; // 根
        }
        dfs(node.right); // 右
    }
    dfs(root);
    return ans;
};