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

波涛澎湃 · · 879 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

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


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

本文来自:简书

感谢作者:波涛澎湃

查看原文:判断一棵二叉树是否是平衡二叉树

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:701969077

879 次点击  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传