0%

CodingInterview-二叉搜索树的第k个结点

思路是对二叉搜索树进行中序遍历,中序遍历的顺序就是节点大小从小到大的顺序,所以只要在求得它的第 k 小的节点的时候返回即可。

下面是递归解法:

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
/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};
*/
class Solution {
public:
TreeNode* KthNode(TreeNode* pRoot, int k)
{
if(k<=0) reutrn NULL;
return this->findNode(pRoot,&k);
}
TreeNode* findNode(TreeNode* pNode,int* k){
if(pNode==NULL) return NULL;
TreeNode* left=this->findNode(pNode->left,k);
if(left!=NULL) return left;
if(--(*k)==0){
return pNode;
}
TreeNode* right=this->findNode(pNode->right,k);
return right;
}
};

这里是循环版本。

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
/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};
*/
class Solution {
public:
TreeNode* KthNode(TreeNode* pRoot, int k)
{
if(pRoot==NULL || k<=0) return NULL;
stack<TreeNode*> s;
TreeNode* cur=pRoot;
while(cur!=NULL || !s.empty()){
while(cur!=NULL){
s.push(cur);
cur=cur->left;
}
if(!s.empty()){
cur=s.top();
s.pop();
if(--k==0) return cur;
cur=cur->right;
}
}
return NULL;
}
};

最后不仅需要注意 pRoot 的边界情况,还要注意 k 的边界情况。