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

所谓平衡二叉树，是指一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

返回真

返回假
递归算法(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
}

最后编辑于：2018.12.20 16:10:14