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

题目

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

思路

1. 递归：由于二叉搜索树的性质是左子节点小于根节点，右子节点又比根节点大，所以我们可以先递归到最左边的子节点，那么这个节点就是最小的节点。从此节点开始计数，刚好就是从大到小排列的了。
2. 用栈的方法中序遍历，可以利用栈来模拟递归遍历，首先根入栈，然后令根节点的左孩子不断入栈直到为空，弹出栈顶，令其右孩子入栈，重复以上操作，直到遍历结束或者访问第k个节点为止。

代码：

递归

/*
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;
    }

    
};

用栈模拟递归

/*
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;
    }

    
};

最后

以上就是寒冷大侠为你收集整理的剑指offer：给定一棵二叉搜索树，请找出其中的第k小的结点。的全部内容，希望文章能够帮你解决剑指offer：给定一棵二叉搜索树，请找出其中的第k小的结点。所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。