c++怎么定義樹的高度

這篇“c++怎么定義樹的高度”文章的知識點(diǎn)大部分人都不太理解，所以小編給大家總結(jié)了以下內(nèi)容，內(nèi)容詳細(xì)，步驟清晰，具有一定的借鑒價值，希望大家閱讀完這篇文章能有所收獲，下面我們一起來看看這篇“c++怎么定義樹的高度”文章吧。

算法：

這一類題目很簡單，不過卻是樹的最基本操作之一，引申為判斷樹是不是平衡二叉樹。

一般做法是，計算二叉樹的左右子樹的高度+1，然后取它們的最大值或者最小值。

題目1:高度平衡二叉樹的定義

代碼實(shí)現(xiàn)：

/** * Definition for a binary tree node. * type TreeNode struct { *     Val int *     Left *TreeNode *     Right *TreeNode * } */ // 一棵平衡二叉樹，左右兩棵子樹的高度差的絕對值不超過1 // 備注：其中任意一個節(jié)點(diǎn)如果不滿足平衡二叉樹時，那么這棵樹就不是平衡二叉樹了，此時我們可以直接返回flasefunc isBalanced(root *TreeNode) bool {    if root == nil { // nil表示的是平衡二叉樹        return true    }    // 1.用來計算當(dāng)前節(jié)點(diǎn)的左右子樹高度差是1    lH := maxDepth(root.Left)    rH := maxDepth(root.Right)    if abs(lH-rH) > 1{        return false    }    // 2. 進(jìn)一步判斷左子樹是不是平衡二叉樹    if !isBalanced(root.Left) {        return false    }    // 3. 進(jìn)一步判斷右子樹是不是平衡二叉樹    return isBalanced(root.Right)}// 典型的計算二叉樹的高度，當(dāng)前左右子樹的最大高度+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:找出二叉樹的最大深度
代碼實(shí)現(xiàn)：

/** * 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}/*遞歸算法：左右子樹的高度最大數(shù)值+1*/

題目3:找出二叉樹的最小深度

代碼實(shí)現(xiàn)：

/** * 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 { // 對于一個孩子的節(jié)點(diǎn)，要計算有孩子節(jié)點(diǎn)的高度        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叉樹的最大深度

代碼實(shí)現(xià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}

以上就是關(guān)于“c++怎么定義樹的高度”這篇文章的內(nèi)容，相信大家都有了一定的了解，希望小編分享的內(nèi)容對大家有幫助，若想了解更多相關(guān)的知識內(nèi)容，請關(guān)注億速云行業(yè)資訊頻道。