c++怎么定义树的高度

发布时间:2022-03-17 16:01:04 作者:iii
来源:亿速云 阅读:233

这篇“c++怎么定义树的高度”文章的知识点大部分人都不太理解,所以小编给大家总结了以下内容,内容详细,步骤清晰,具有一定的借鉴价值,希望大家阅读完这篇文章能有所收获,下面我们一起来看看这篇“c++怎么定义树的高度”文章吧。

算法:

这一类题目很简单,不过却是树的最基本操作之一,引申为判断树是不是平衡二叉树。

一般做法是,计算二叉树的左右子树的高度+1,然后取它们的最大值或者最小值。

题目1:高度平衡二叉树的定义

代码实现:

/** * Definition for a binary tree node. * type TreeNode struct { *     Val int *     Left *TreeNode *     Right *TreeNode * } */ // 一棵平衡二叉树,左右两棵子树的高度差的绝对值不超过1 // 备注:其中任意一个节点如果不满足平衡二叉树时,那么这棵树就不是平衡二叉树了,此时我们可以直接返回flasefunc isBalanced(root *TreeNode) bool {    if root == nil { // nil表示的是平衡二叉树        return true    }    // 1.用来计算当前节点的左右子树高度差是1    lH := maxDepth(root.Left)    rH := maxDepth(root.Right)    if abs(lH-rH) > 1{        return false    }    // 2. 进一步判断左子树是不是平衡二叉树    if !isBalanced(root.Left) {        return false    }    // 3. 进一步判断右子树是不是平衡二叉树    return isBalanced(root.Right)}// 典型的计算二叉树的高度,当前左右子树的最大高度+1func maxDepth(root *TreeNode) int {    if root == nil {         return 0    }    return max(maxDepth(root.Left),maxDepth(root.Right)) + 1}func max(a,b int) int {    if a > b {        return a    }    return b}func abs(a int) int {    if a < 0 {        return -a    }    return a}

题目2:找出二叉树的最大深度
代码实现:

/** * Definition for a binary tree node. * type TreeNode struct { *     Val int *     Left *TreeNode *     Right *TreeNode * } */func maxDepth(root *TreeNode) int {    if root == nil {        return 0    }    left := maxDepth(root.Left)    right := maxDepth(root.Right)    if left > right {        return left + 1    }    return right + 1}/*递归算法:左右子树的高度最大数值+1*/

题目3:找出二叉树的最小深度

代码实现:

/** * Definition for a binary tree node. * type TreeNode struct { *     Val int *     Left *TreeNode *     Right *TreeNode * } */func minDepth(root *TreeNode) int {    if root == nil {        return 0    }    if root.Left ==nil && root.Right == nil {        return 1    }    min := int(^uint(0) >> 1)    if root.Left != nil { // 对于一个孩子的节点,要计算有孩子节点的高度        h := minDepth(root.Left)        if min > h {            min = h        }    }    if root.Right != nil {        h := minDepth(root.Right)        if min > h {            min = h        }    }    return min+1}

题目4:N叉树的最大深度

代码实现:

/** * Definition for a Node. * type Node struct { *     Val int *     Children []*Node * } */func maxDepth(root *Node) int {    if root == nil {        return 0    }    var hs []int    for _, n := range root.Children {        h := maxDepth(n)        hs = append(hs,h)    }    max := 0    for _,h:=range hs {        if h > max {            max = h        }    }        return max + 1}

以上就是关于“c++怎么定义树的高度”这篇文章的内容,相信大家都有了一定的了解,希望小编分享的内容对大家有帮助,若想了解更多相关的知识内容,请关注亿速云行业资讯频道。

推荐阅读:
  1. 高度平衡的二叉搜索树—AVLTree
  2. Btree(B-树)---C++

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

c++

上一篇:c++中摩尔投票法如何使用

下一篇:c++如何删除链表中重复节点

相关阅读

您好,登录后才能下订单哦!

密码登录
登录注册
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》