首页 » C++ » 剑指Offer(54)二叉搜索树的第K大结点

剑指Offer(54)二叉搜索树的第K大结点

原文 http://blog.csdn.net/Haiqiang1995/article/details/79167133

2018-01-26 02:00:33阅读(368)

题目描述
给定一颗二叉搜索树,请找出其中的第k大的结点。例如, 5 / \ 3 7 /\ /\ 2 4 6 8 中,按结点数值大小顺序第三个结点的值为4。

算法:递归算法 数据结构:二叉搜索树 编程语言:C++
 /*
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==nullptr||k==0)//空值检测
            return nullptr;
        return KthCore(pRoot,k);//防止每次递归都进行空值检测,并增强函数的复用性
    }
    int count=0;
    TreeNode* KthCore(TreeNode* pRoot,int k)
    {
        TreeNode* target=nullptr;//目标的返回值
        //遍历左子树
        if(pRoot->left!=nullptr)
        {
            target=KthCore(pRoot->left,k);
        }
        count++;
        if(target==nullptr)
        {
            if(count==k)
            {
                target=pRoot;
                return target;
            }
        }
        //遍历右子树
        if(target==nullptr&&pRoot->right!=nullptr)
        {
            target=KthCore(pRoot->right,k);
        }
        return target;
    }
};

最新发布

CentOS专题

关于本站

5ibc.net旗下博客站精品博文小部分原创、大部分从互联网收集整理。尊重作者版权、传播精品博文,让更多编程爱好者知晓!

小提示

按 Ctrl+D 键,
把本文加入收藏夹