【BinarySearch】 230. Kth Smallest Element in a BST

寻找二叉排序树中第k大值。  题目: https://leetcode.com/problems/kth-smallest-element-in-a-bst/description/

 

 

 

 

给一个二叉 搜索/排序 树。寻找它的第k大值。

二叉排序树的性质,中序遍历结果就是排好序的序列。      深度优先遍历。神奇的过了。。

 

discuss中提供了 二分搜索,   深度优先搜索 的递归版和迭代版。   。。这个题应该是要用二分做的。。。毕竟放在二分分类里面。

 

因为二叉排序树结点的左边都小于它,右边都大于它。  先统计一个结点的左子树部分结点个数count。如果count大于等于当前的k。 说明第k大值在左半部分,不必搜索右部。否则在右边搜索第k-1-count 大值。(  1为当前结点计数。   countNodes方法用来统计结点个数。

 

 

最后一个是迭代版的 dfs。  直接复制代码过来。    就是递归版做递归消除