判断一棵二叉树是否是平衡二叉树

所谓平衡二叉树,是指一 棵空树或它的左右两个子树的高度差的绝对值不超过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
}

有疑问加站长微信联系(非本文作者)

• 请尽量让自己的回复能够对别人有帮助
• 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
• 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
• 图片支持拖拽、截图粘贴等方式上传