剑指offer：给定一棵二叉搜索树，请找出其中的第k小的结点。

89 阅读 0 评论 59 点赞

我是靠谱客的博主寒冷大侠，这篇文章主要介绍剑指offer：给定一棵二叉搜索树，请找出其中的第k小的结点。，现在分享给大家，希望可以做个参考。

题目

给定一棵二叉搜索树，请找出其中的第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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
class Solution {
public:
    int count = 0;
    TreeNode *node = NULL;
    void dfs(TreeNode* root, int k){
//         如果root为NULL节点 直接退回
        if(!root)
            return ;
//         一开始会退回到最左边的节点 此时 刚好会count+1，那么count等于几就是第几个大的节点了
        dfs(root->left,k);
        count++;
        if(count==k){
            node = root;
        }
        else if(count>k){
//             大于k就退回
            return ;
        }else{
//             如果小于k就看右边的节点是不是刚好等于k的
            dfs(root->right,k);
        }
        
            
    }
    TreeNode* KthNode(TreeNode* pRoot, int k)
    {
        dfs(pRoot,k);
        return node;
    }

    
};

用栈模拟递归

复制代码

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
35
36
37
38
39
/*
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)
            return nullptr;
        TreeNode* root = pRoot;
        
        stack<TreeNode *> s;
        
        while(!s.empty() || root){
            while(root){
                s.push(root);
                root = root->left;
            }
            k--;
            TreeNode* node = s.top();
            s.pop();
            if(k==0){
               return node;
            }
            root = node->right;
        }
      return nullptr;
    }

    
};