题目

给定一个二叉搜索树，请找出第k大的节点。（leetcode230）

答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    TreeNode* Kth(TreeNode* pRoot,int& target)
    {
        TreeNode* t=NULL;
        if(pRoot->left)  t=Kth(pRoot->left,target);
        target--;
        if(target==0) 
        {
            t =pRoot;
        }
        if(t==NULL && pRoot->right) t =Kth(pRoot->right,target);
        return t;
    }
    int kthSmallest(TreeNode* pRoot, int k)
        {
            if(pRoot==nullptr||k<=0) return 0;
            TreeNode* node = Kth(pRoot,k);
            return node->val;
        }
};

思路

一道递归题，在参数传递的问题上想了很久，也试了很久，

因为要在递归中传递要得到的节点，所以在递归开始先设置一个空指针，经过运算，最后返回这个指针。