【62】二叉搜索树的第k个结点

【62】二叉搜索树的第k个结点

参与人数：2376时间限制：1秒空间限制：32768K

题目描述 给定一颗二叉搜索树，请找出其中的第k大的结点。 例如， 5 / \ 3 7 /\ /\ 2 4 6 8 中，按结点数值大小顺序第三个结点的值为4。 牛客网题目链接：点击这里

---

VS2010代码：

// Source: http://www.nowcoder.com/practice/ef068f602dde4d28aab2b210e859150a?rp=0&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking // Author: Yang Qiang // Date : 2016-8-14 #include<iostream> #include<vector> using namespace std; struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) { } }; //方法一：全部排序 class Solution { vector<TreeNode*> nums; void DFS(TreeNode* p) { if(!p) { return; } else { DFS(p->left); nums.push_back(p); DFS(p->right); } } public: TreeNode* KthNode(TreeNode* pRoot, unsigned int k) { if(!pRoot) return NULL; int n=0; DFS(pRoot); if(k<=nums.size() && k!=0) //题目要求k为1-n。所以要排除0 return nums[k-1]; else return NULL; } };

///方法二：找到即返回

可设置一个计数器，而不用容器存储，找到即返回。

牛客网通过图片：