// ++++++++++++++++++++++++++++++++++++++++
// 《零基础Go语言算法实战》源码
// ++++++++++++++++++++++++++++++++++++++++
// Author:廖显东（ShirDon）
// Blog:https://www.shirdon.com/
// Gitee:https://gitee.com/shirdonl/goAlgorithms.git
// Buy link :https://item.jd.com/14101229.html
// ++++++++++++++++++++++++++++++++++++++++

package main

import "fmt"

// 具有整数值的二叉树中的节点
type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

// 检查二叉树是否平衡
func isBalanced(root *TreeNode) bool {
	if root == nil {
		return true
	}

	//获取左右子树的高度
	leftHeight := getHeight(root.Left)
	rightHeight := getHeight(root.Right)

	//如果高度之间的差异大于 1，则树不平衡
	if abs(leftHeight-rightHeight) > 1 {
		return false
	}

	//递归检查左右子树是否平衡
	return isBalanced(root.Left) && isBalanced(root.Right)
}

// 返回以给定节点为根的二叉树的高度
func getHeight(node *TreeNode) int {
	if node == nil {
		return 0
	}

	//获取左右子树的高度
	leftHeight := getHeight(node.Left)
	rightHeight := getHeight(node.Right)

	//返回左右子树的最大高度，根节点加 1
	return max(leftHeight, rightHeight) + 1
}

// 返回 x 的绝对值
func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

// 返回 x 和 y 的最大值
func max(x, y int) int {
	if x > y {
		return x
	}
	return y
}

func main() {
	root := &TreeNode{
		Val: 1,
		Left: &TreeNode{
			Val: 2,
			Left: &TreeNode{
				Val: 4,
			},
			Right: &TreeNode{
				Val: 5,
			},
		},
		Right: &TreeNode{
			Val: 3,
			Left: &TreeNode{
				Val: 6,
			},
			Right: &TreeNode{
				Val: 7,
			},
		},
	}

	fmt.Println(isBalanced(root))
}

//$ go run interview10-3.go
//true