[Jianzhi offer] 54 The k-th node of binary search tree

The finger of the sword Offer 54. The second of binary search tree k Big node

subject

Given a binary search tree , Please find the first one k Large node value .

Ideas

  Traverse the reverse order of the... According to the middle order of the binary search tree K Nodes

Code

/** * 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 res;
    int kthLargest(TreeNode* root, int k) {
    
        dfs(root,k);
        return res;
    }

    void dfs(TreeNode *root, int &k)
    {
    

        //  In the sequence traversal   In reverse order ： Right node -> Root node -> The left node 
        if(!root) return ;

        dfs(root->right,k);
        k--;
        if(!k) res = root->val;  //  When k be equal to 0  Description target node found   There is no need to continue traversing 
        dfs(root->left,k);//  Left 
    }

};