二叉树应用_二叉搜索树的第K个节点

约定不等于承诺〃 2022-05-22 05:04 149阅读 0赞

题目：给定一颗二叉搜索树，请找出其中的第k大的结点。例如， 5 / \\ 3 7 /\\ /\\ 2 4 6 8 中，按结点数值大小顺序第三个结点的值为4。  
分析：进行中序遍历，中序遍历序列的数值是递增排序的。

/*
    struct TreeNode {
        int val;
        struct TreeNode *left;
        struct TreeNode *right;
        TreeNode(int x) :
                val(x), left(NULL), right(NULL) {
        }
    };
    */
    class Solution {
        int number=0;
    public:
    //多想想，如何逐层外传的
        TreeNode* KthNode(TreeNode* pRoot, int k)
        {
            if(pRoot)
            {
                TreeNode* node=KthNode(pRoot->left,k);
                if(node!=NULL)
                    return node;
                ++number;
                if(number==k)
                    return pRoot;
                node=KthNode(pRoot->right,k);
                if(node!=NULL)
                    return node;
            }
            return NULL;
        }
    
    /*
    //中序遍历的结果就是有序序列，第K个元素就是vec[K-1]存储的节点指针；
        TreeNode* KthNode(TreeNode* pRoot, unsigned int k)
        {
            if(pRoot==NULL||k<=0) return NULL;
            vector<TreeNode*> vec;
            Inorder(pRoot,vec);
            if(k>vec.size())
                return NULL;
            return vec[k-1];
        }
        //中序遍历，将节点依次压入vector中
        void Inorder(TreeNode* pRoot,vector<TreeNode*>& vec)
        {
            if(pRoot==NULL) return;
            Inorder(pRoot->left,vec);
            vec.push_back(pRoot);
            Inorder(pRoot->right,vec);
        } 
      */
    };

发表评论取消回复

表情：

评论列表（有 0 条评论，149人围观）

还没有评论，来说两句吧...

相关阅读

相关二叉搜索树、平衡二叉树

一、二叉搜索树这里我们不用太多书面化的语言来定义，笔者认为在讨论数据结构、算法相关的内容时用太多书面化、学术化的语言是一种让人很烦的事情。咬文嚼字，不便于读者理解。

阳光穿透心脏的1/2处/ 2023年10月18日 22:26/ 0 赞/ 18 阅读

相关（Java 剑指 offer）二叉搜索树的第 k 个节点

文章目录一、题目解析二、代码三、总结一、题目解析给定一棵二叉搜索树，请找出其中的第 k 小的结点。例如，（5，

桃扇骨/ 2022年12月11日 15:09/ 0 赞/ 108 阅读

相关二叉搜索树第k大个节点

面试题63：给定一颗二叉搜索树，请找出其中的第k大的节点 //二叉搜索树的第k大节点 BinaryTreeNode getKthNode(BinaryTree

矫情吗；*/ 2022年06月17日 07:08/ 0 赞/ 138 阅读

相关剑指offer_二叉搜索树的第k个节点

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

谁借莪１个温暖的怀抱￠/ 2022年06月09日 06:56/ 0 赞/ 129 阅读

相关二叉搜索树的第k个结点

![这里写图片描述][70] import java.util.; class TreeNode { int val = 0;

梦里梦外;/ 2022年05月24日 10:35/ 0 赞/ 148 阅读

相关二叉树应用_二叉搜索树的第K个节点

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

约定不等于承诺〃/ 2022年05月22日 05:04/ 0 赞/ 150 阅读

相关二叉树应用_二叉树的下一个节点

题目：给定一个二叉树和其中的一个节点，找出中序遍历的下一个节点。树中的节点除了有指向左右节点的两个指针之外，还有一个指向父节点的指针。分析：对于这个问题分情况讨论，1、如

淡淡的烟草味﹌/ 2022年05月22日 04:07/ 0 赞/ 179 阅读

相关二叉搜索树第k大的节点

题目描述给定一个二叉搜索树，找出其中第k大的节点![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_tex

今天药忘吃喽~/ 2022年04月05日 06:14/ 0 赞/ 166 阅读

相关剑指offer: 二叉搜索树的第K个节点

题目描述给定一棵二叉搜索树，请找出其中的第k小的结点。例如，（5，3，7，2，4，6，8）中，按结点数值大小顺序第三小结点的值为4。解题思路：对于二叉搜索树

青旅半醒/ 2022年02月25日 15:48/ 0 赞/ 170 阅读

相关二叉搜索树的第k个节点

题目描述给定一棵二叉搜索树，请找出其中的第k小的结点。例如，（5，3，7，2，4，6，8）中，按结点数值大小顺序第三小结点的值为4。原理是中序遍历，

た入场券/ 2022年02月02日 06:21/ 0 赞/ 152 阅读