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

vlambda
2021-04-16

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

福大大答案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 }}