判定平衡二叉树

题干

图片.png

代码

package main

import (
    "fmt"
    "math"
)

// TreeNode 树节点对象
type TreeNode struct {
    Val   int       // 值节点
    Left  *TreeNode // 左子树
    Right *TreeNode // 右子树
}

func getTreeHeight(root *TreeNode) int {
    if root == nil {
        return 0
    }

    left := root.Left
    right := root.Right
    lh := getTreeHeight(left)
    rh := getTreeHeight(right)
    if lh >= 0 && rh >= 0 && int(math.Abs(float64(lh-rh))) <= 1 {
        return int(math.Max(float64(lh), float64(rh))) + 1
    }
    return -1
}

// IsBalanced 是否平衡二叉树
func IsBalanced(root *TreeNode) bool {
    return getTreeHeight(root) >= 0
}

func main() {
    root := &TreeNode{
        Val: 3,
        Left: &TreeNode{
            Val: 9,
        },
        Right: &TreeNode{
            Val: 20,
            Left: &TreeNode{
                Val: 15,
            },
            Right: &TreeNode{
                Val: 7,
            },
        },
    }

    isBalanced := IsBalanced(root)
    if isBalanced {
        fmt.Println(root, "是一棵平衡二叉树")
    } else {
        fmt.Println(root, "不是一棵平衡二叉树")
    }
}