判断二叉树是否是平衡二叉树？
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
}
}执行结果如下：
