二叉搜索树的第k个结点
Desicription
给定一颗二叉搜索树,请找出其中的第k大的结点。按结点数值大小顺序第三个结点的值为4。
Solution
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34
|
class Solution { private: TreeNode* res = nullptr; int currentCount = 0; bool foundFLag = false; void OnSearch(TreeNode* pRoot, int k) { if(!pRoot || foundFLag) { return ; } OnSearch(pRoot->left, k); currentCount++; if(currentCount == k) { res = pRoot; foundFLag = true; return ; } OnSearch(pRoot->right, k); } public: TreeNode* KthNode(TreeNode* pRoot, int k) { OnSearch(pRoot, k); return res; } };
|