二叉搜索树的第k个节点

发表于 | 分类于

题目

给定一棵二叉搜索树，请找出其中的第k小的结点。例如， （5，3，7，2，4，6，8） 中，按结点数值大小顺序第三小结点的值为4。

思路

二叉搜索树的中序遍历即为从小到大排列

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
function KthNode(pRoot, k) {
  if (pRoot === null || k === 0) {
    return null;
  }
  // 为了能追踪k，应该把KthNodeCore函数定义在这里面，k应该在KthNodeCore函数外面
  function KthNodeCore(pRoot) {
    let target = null;
    if (pRoot.left !== null) {
      target = KthNodeCore(pRoot.left, k);
    }
    if (target === null) {
      if (k === 1) {
        target = pRoot;
      }
      k--;
    }
    if (target === null && pRoot.right !== null) {
      target = KthNodeCore(pRoot.right, k);
    }
    return target;
  }
  return KthNodeCore(pRoot);
}