题目描述:
给定一颗二叉搜索树,请找出其中的第k大的结点。
例如, 5 / 3 7 / / 2 4 6 8 中,按结点数值大小顺序第三个结点的值为4
分析:
二叉搜索树中序遍历就是从小到大。只要遍历k个结点就可以了。
代码:
1 /* 2 struct TreeNode { 3 int val; 4 struct TreeNode *left; 5 struct TreeNode *right; 6 TreeNode(int x) : 7 val(x), left(NULL), right(NULL) { 8 } 9 }; 10 */ 11 class Solution { 12 public: 13 int cnt = 0; 14 TreeNode* KthNode(TreeNode* pRoot, int k) { 15 if(pRoot) { 16 TreeNode* kthNode = KthNode(pRoot->left, k); 17 if(kthNode) return kthNode; 18 if(++cnt == k) return pRoot; 19 kthNode = KthNode(pRoot->right, k); 20 if(kthNode) return kthNode; 21 } 22 return NULL; 23 } 24 };