题目描述

• 给定一颗二叉搜索树，请找出其中第 k 大的节点

• 例如，在下图中所示二叉搜索树中，按节点数值大小顺序，第三大节点的值是 4

题目解读

• 剑指Offer 269
• LeetCode 230. Kth Smallest Element in a BST

代码

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 大节点时候才会执行