问题

返回BST的第k大节点

算法：DFS逆中序遍历

按右-中-左的顺序遍历，每个节点k–, 记录k==0的节点值即可。需要传入k的引用，同时可以剪枝：在边界处特判k是否为0

时间复杂度

$O(N)$

代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int ans;
    int kthLargest(TreeNode* root, int k) {
        dfs(root, k);
        return ans;
    }
    void dfs(TreeNode *root, int& k){
        if(!k || !root) return;

        dfs(root->right,k);
        k --;
        if(k == 0){
            ans = root->val;
            return;
        }
        dfs(root->left, k);

    }
};