题目描述
给定一棵二叉搜索树，请找出其中的第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; }
