【剑指Offer】JZ62二叉搜索树的第K个结点

题目地址：牛客网
题目：

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

示例1

输入
{5,3,7,2,4,6,8},3
返回值
{4}

说明

按结点数值大小顺序第三小结点的值为4

思路：
中序遍历二叉搜索树，第k小的结点是中序遍历的第k个结点。

代码：

/*
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)
    {
        TreeNode *stack[10001];
        int top = -1;
        TreeNode *p = pRoot;
        int i=1;
        while(p!=NULL||top!=-1){
            if(p!=NULL){
                stack[++top]=p;
                p=p->left;
            }else{
                p=stack[top--];
                if(i==k){
                    return p;
                    break;
                }
                i++;
                p=p->right;
            }
        }
        return NULL;
    }
};

最后

以上就是潇洒鸵鸟为你收集整理的【剑指Offer】JZ62二叉搜索树的第K个结点的全部内容，希望文章能够帮你解决【剑指Offer】JZ62二叉搜索树的第K个结点所遇到的程序开发问题。

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