题目描述

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

分析

二叉搜索树的特点就是对于某个点来说，左子树上的点小于该点，右子树上的点大于该点。所以按照中序遍历的方法得到的序列即是从小到大的序列。

代码

/* function TreeNode(x) {    this.val = x;    this.left = null;    this.right = null;} */function KthNode(r, k){    if(r === null)        return null;    var res = [];    var s = [];    var cur = r;        while(cur !== null || s.length !== 0) {        if(cur !== null){            s.push(cur);            cur = cur.left;        }else{            cur = s.pop();            res.push(cur);            if(res.length === k)                return res.pop();            cur = cur.right;        }    }        return null;}