我是靠谱客的博主 潇洒鸵鸟,这篇文章主要介绍【剑指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二叉搜索树内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(56)

评论列表共有 0 条评论

立即
投稿
返回
顶部