62.二叉搜索树的第k个结点

题目描述：

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

知识点：

• 二叉树的中序遍历

  解题思路：

• 通过观察我们可以发现，这课二叉树的中序遍历恰好是按从小到大的顺序排列的，所以这道题实际考察的是二叉树的中序遍历

解题代码：

• 递归版 ```javascript // 中序遍历递归版

function KthNode(pRoot, k) { // write code here if(!pRoot) return null; const res = []; const midOreder = (node) => { if(node.left) preOreder(node.left); res.push(node); if(node.right) preOreder(node.right); } preOreder(pRoot) return res[k-1]; }

- 非递归版
```javascript
// 中序遍历非递归版
function KthNode(pRoot, k)
{
    // write code here
    if(!pRoot) return null;
    const res = [];
    const stack = [];
    let p = pRoot;
    while (stack.length || p) {
        while(p) {
            stack.push(p);
            p = p.left;
        }
        let temp = stack.pop();
        res.push(temp);
        p = temp.right;
    }
    return res[k-1];
}