剑指Offer JZ62 二叉搜索树的第k个结点（JavaScript）

72 阅读 0 评论 48 点赞

我是靠谱客的博主包容诺言，这篇文章主要介绍剑指Offer JZ62 二叉搜索树的第k个结点（JavaScript），现在分享给大家，希望可以做个参考。

时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M 热度指数：482786
本题知识点：树

题目描述
给定一棵二叉搜索树，请找出其中的第k小的TreeNode结点。
示例1
输入
{5,3,7,2,4,6,8},3
返回值
{4}
说明
按结点数值大小顺序第三小结点的值为4

思路：中序遍历得到从小到大排序的数组，读取第k-1个即可

/* function TreeNode(x) {
    this.val = x;
    this.left = null;
    this.right = null;
} */
function KthNode(pRoot, k) {
    let arr = []
    dfs(pRoot, arr)
    return arr[k - 1]
}

function dfs(root, arr) {
    if (!root) return null
    if (root.left) dfs(root.left, arr)
    arr.push(root)
    if (root.right) dfs(root.right, arr)
}