题目描述
- 给定一颗二叉搜索树，请找出其中第 k 大的节点
-
例如，在下图中所示二叉搜索树中，按节点数值大小顺序，第三大节点的值是 4
题目解读
代码
class Solution {
public:
int count = 0;
TreeNode* KthNode(TreeNode* pRoot, int k)
{
if(pRoot){
TreeNode *node = KthNode(pRoot -> left, k);
if(node){
return node;
}
count ++;
if(count == k){
return pRoot;
}
node = KthNode(pRoot -> right, k);
if(node){
return node;
}
}
return NULL;
}
};
总结展望
- 关于这道题，重点讲解一下，不知道是因为最近因为开题，十天半个月没刷题还是咋的，感觉思维特迟钝，这道题竟然思考了一个晚上加一个上午，愣是刚才茅塞顿开才搞定，所以刷题大业要持之以恒，不可荒废啊
- 这道题目是应用二叉树的中序遍历来做的，啥是中序遍历呢，简言之就是依次遍历左孩子，根节点，右孩子，然后递归执行，遍历即可，但是呢，这又可一般的中序遍历不一样，像我们一般用递归中序遍历，直接无返回值，直接递归四行代码即可，现在要返回值，它要是第k大的那个节点，注意不知节点值，是节点。
- 这就很尴尬了，要节点，不要节点值，所以呢，我们要返回值，要判断返回值，感觉有种只可意会不可言传的感觉，语言真是不好描述，提醒几点吧。
- 第一，代码中的 return NIULL;这句话无论 if 是否执行，这句是肯定要执行的，所以呢，只要返回不是第 K 大节点，这句话都会执行
- 第二，if(node) return node，这句话用来依次向上一级返回第 K 大节点。只有在返回第 K 大节点时候才会执行
