c++怎么定义树的高度

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

创新互联专注为客户提供全方位的互联网综合服务,包含不限于网站建设、成都网站制作、简阳网络推广、小程序制作、简阳网络营销、简阳企业策划、简阳品牌公关、搜索引擎seo、人物专访、企业宣传片、企业代运营等,从售前售中售后,我们都将竭诚为您服务,您的肯定,是我们最大的嘉奖;创新互联为所有大学生创业者提供简阳建站搭建服务,24小时服务热线:13518219792,官方网址:www.cdcxhl.com

算法:

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

一般做法是,计算二叉树的左右子树的高度+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++怎么定义树的高度”这篇文章的内容,相信大家都有了一定的了解,希望小编分享的内容对大家有帮助,若想了解更多相关的知识内容,请关注创新互联行业资讯频道。


当前文章:c++怎么定义树的高度
当前路径:http://scyanting.com/article/ihoood.html