所谓平衡二叉树,是指一 棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。
3
/ \
9 20
/ \
15 7
返回真
1
/ \
2 2
/ \
3 3
/ \
4 4
返回假
递归算法(golang):
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func isBalanced(root *TreeNode) bool {
if root == nil {
return true
}
if isBalanced(root.Left) == false {
return false
}
if isBalanced(root.Right) == false {
return false
}
if abs(maxDepth(root.Left) - maxDepth(root.Right)) > 1 {
return false
}
return true
}
func maxDepth(root *TreeNode) int {
if root == nil {
return 0
}
return max(maxDepth(root.Left), maxDepth(root.Right)) + 1
}
func max(x, y int) int {
if x >= y {
return x
}
return y
}
func abs(x int) int {
if x < 0 {
return -x
}
return x
}
普通循环:
package main
import (
"fmt"
"math"
)
//判断一棵树是否是平衡二叉树
func main() {
//var bt1 *BinaryTree = &BinaryTree{data: 1, left: nil, right: nil}
var bt7 *BinaryTree = &BinaryTree{data: 7, left: nil, right: nil}
var bt15 *BinaryTree = &BinaryTree{data: 15, left: nil, right: nil}
var bt20 *BinaryTree = &BinaryTree{data: 20, left: bt15, right: bt7}
var bt9 *BinaryTree = &BinaryTree{data: 9, left: nil, right: nil}
var bt3 *BinaryTree = &BinaryTree{data: 3, left: bt9, right: bt20}
// fmt.Println(bt3.verifyIfBalanceBT)
fmt.Println(bt3.verifyIfBalanceBT())
}
//BinaryTree 二叉树
type BinaryTree struct {
data int
left *BinaryTree
right *BinaryTree
}
func (bt *BinaryTree) verifyIfBalanceBT() bool {
if bt == nil {
return true
}
root := bt
for root.left != nil {
if math.Abs(float64(root.getLeftH()-root.getRightH())) <= 1 {
// root.left.verifyIfBalanceBT()
root = root.left
} else {
return false
}
}
root = bt
for root.right != nil {
if math.Abs(float64(root.getLeftH()-root.getRightH())) <= 1 {
root = root.right
} else {
return false
}
}
return true
}
func (bt *BinaryTree) getLeftH() int {
if bt.left == nil {
return 0
}
height := 1
root := bt.left
for root.left != nil {
height++
root = root.left
}
return height
}
func (bt *BinaryTree) getRightH() int {
if bt.right == nil {
return 0
}
height := 1
root := bt.right
for root.right != nil {
height++
root = root.right
}
return height
}
有疑问加站长微信联系(非本文作者)
![](https://static.golangjob.cn/static/img/footer.png?imageView2/2/w/280)