2021-04-13：判断二叉树是否是平衡二叉树？

福大大架构师每日一题 · · 437 次点击 · · 开始浏览

这是一个创建于的文章，其中的信息可能已经有所发展或是发生改变。

福大大答案2021-04-13：

1.左子节点平衡。
2.右子节点平衡。
3.左右子节点高度差不超过1。
采用递归即可。

代码用golang编写。代码如下：

package main

import "fmt"

func main() {
    head := &TreeNode{Val: 5}
    head.Left = &TreeNode{Val: 3}
    head.Right = &TreeNode{Val: 7}
    head.Left.Left = &TreeNode{Val: 2}
    head.Left.Right = &TreeNode{Val: 4}
    head.Right.Left = &TreeNode{Val: 6}
    head.Right.Right = &TreeNode{Val: 8}
    ret := IsBalanced(head)
    fmt.Println("是否是平衡树：", ret)
}

//Definition for a binary tree node.
type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}
type Info struct {
    IsBalanced bool
    Height     int
}

func IsBalanced(head *TreeNode) bool {
    return process(head).IsBalanced
}

func process(head *TreeNode) *Info {
    if head == nil {
        return &Info{IsBalanced: true}
    }

    leftInfo := process(head.Left)
    //左不平衡
    if !leftInfo.IsBalanced {
        return leftInfo
    }

    rightInfo := process(head.Right)
    //右不平衡
    if !rightInfo.IsBalanced {
        return rightInfo
    }

    //高度差大于1
    if Abs(leftInfo.Height, rightInfo.Height) > 1 {
        return new(Info)
    }

    //通过所有考验
    return &Info{IsBalanced: true, Height: GetMax(leftInfo.Height, rightInfo.Height) + 1}

}
func GetMax(a int, b int) int {
    if a > b {
        return a
    } else {
        return b
    }
}
func Abs(a int, b int) int {
    if a > b {
        return a - b
    } else {
        return b - a
    }
}

执行结果如下：