剑指 Offer 54. 二叉搜索树的第k大节点

题目 给定一棵二叉搜索树，请找出其中第k大的节点。 题解 好久没打代码了，练练手，知识点题目，中序遍历。 递归

class Solution { public: int ans = 0; int cnt = 0; int kthLargest(TreeNode* root, int k) { dfs(root,k); return ans; } void dfs(TreeNode* root,int k){ if(root==nullptr) return ; if(root->right) dfs(root->right,k); cnt++; if(cnt==k) ans=root->val; if(root->left) dfs(root->left,k); } };

单函数递归

class Solution { public: int cnt = 0; int kthLargest(TreeNode* root, int k) { if(root == nullptr) return -1; int ans = 0; if(root->right) ans = kthLargest(root->right,k); if(cnt >= k) return ans; cnt++; if(cnt==k) return root->val; if(root->left) return kthLargest(root->left,k); return -1; } };

迭代

class Solution { public: int cnt = 0; int kthLargest(TreeNode* root, int k) { if(root == nullptr) return -1; int ans = 0; if(root->right) ans = kthLargest(root->right,k); if(cnt >= k) return ans; cnt++; if(cnt==k) return root->val; if(root->left) return kthLargest(root->left,k); return -1; } };

对节点加变量 int sum 表示该节点子树大小

class Solution { public: int kthLargest(TreeNode* root, int k) { if(root == nullptr) return -1; int sum = 0; if(root->right==nullptr) sum = 0; else sum = root->right->sum + 1; if(sum + 1 == k){ return root->val; }else if(sum > k){ return kthLargest(root->right,k); }else{ return kthLargest(root->left,k-sum); } } };