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

题目描述

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

分析

二叉搜索树的中序遍历结果是有序的，使用中序遍历，每遍历一个节点，k-1,直到k减到1，即为第K小的节点

代码

/* function TreeNode(x) {
    this.val = x;
    this.left = null;
    this.right = null;
} */
function KthNode(pRoot, k){
    if(!pRoot || !k){
        return null;
    }
    return Kth(pRoot);
}
function Kth(node){
        var res = null;
        if(node.left){
            res = Kth(node.left);
        }
        if(!res){
            if(k === 1)
                res = node;
            k--;
        }
        if(!res && node.right)
            res = Kth(node.right);
        return res;
    }