c++怎么计算二叉搜索树中第K小的元素-成都创新互联网站建设

关于创新互联

多方位宣传企业产品与服务 突出企业形象

公司简介 公司的服务 荣誉资质 新闻动态 联系我们

c++怎么计算二叉搜索树中第K小的元素

这篇文章主要讲解了“c++怎么计算二叉搜索树中第K小的元素”,文中的讲解内容简单清晰,易于学习与理解,下面请大家跟着小编的思路慢慢深入,一起来研究和学习“c++怎么计算二叉搜索树中第K小的元素”吧!

成都创新互联-专业网站定制、快速模板网站建设、高性价比呼玛网站开发、企业建站全套包干低至880元,成熟完善的模板库,直接使用。一站式呼玛网站制作公司更省心,省钱,快速模板网站建设找我们,业务覆盖呼玛地区。费用合理售后完善,十载实体公司更值得信赖。

算法:

这类题目的核心思想是,利用二叉树的中序遍历是从小到大的,将其转变成数组,然后对这个有序数组进行取值操作就可以了。

特别注意:转换之后的数组有可能会存在重复的节点,此时的话,我们就需要对数组进行去重的操作。

题目1:二叉树中第二小的节点

代码实现:

/** * Definition for a binary tree node. * type TreeNode struct { *     Val int *     Left *TreeNode *     Right *TreeNode * } */func findSecondMinimumValue(root *TreeNode) int {    res := midOrder(root)    m := make(map[int]int)    for _,v:=range res {        m[v] = v    }       resp := []int{}    for _,v:=range m {        resp = append(resp,v)    }    if len(resp)>=2{        sort.Ints(resp)        return resp[1]    }    return -1}func midOrder(root *TreeNode) (res []int) {    if root == nil {        return    }    res = append(res,midOrder(root.Left)...)    res = append(res,root.Val)    res = append(res,midOrder(root.Right)...)    return}

题目2:二叉搜索树中第K小的元素

代码实现:

/** * Definition for a binary tree node. * type TreeNode struct { *     Val int *     Left *TreeNode *     Right *TreeNode * } */func kthSmallest(root *TreeNode, k int) int {    if root == nil {        return 0    }    res := midOrder(root)     if k > len(res) {        return 0    }    return res[k-1]}func midOrder(root *TreeNode) []int {    if root == nil {        return nil    }    res := []int{}    res = append(res,midOrder(root.Left)...)    res = append(res,root.Val)    res = append(res,midOrder(root.Right)...)    return res }

感谢各位的阅读,以上就是“c++怎么计算二叉搜索树中第K小的元素”的内容了,经过本文的学习后,相信大家对c++怎么计算二叉搜索树中第K小的元素这一问题有了更深刻的体会,具体使用情况还需要大家实践验证。这里是创新互联,小编将为大家推送更多相关知识点的文章,欢迎关注!


网站名称:c++怎么计算二叉搜索树中第K小的元素
网站地址:http://kswsj.cn/article/pojhid.html

其他资讯