c++怎么定义树的高度

这篇“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++怎么定义树的高度”这篇文章的内容，相信大家都有了一定的了解，希望小编分享的内容对大家有帮助，若想了解更多相关的知识内容，请关注亿速云行业资讯频道。