题解 | #判断是不是平衡二叉树#

package main

import . "nc_tools"
import "math"

/*
 * type TreeNode struct {
 *   Val int
 *   Left *TreeNode
 *   Right *TreeNode
 * }
 */

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param pRoot TreeNode类
 * @return bool布尔型
 */


// 解题思路： 
// 递归获取左右子树的高度，判断左右子树是不是相差不超过1
// 递归判断左右子树是否是平衡二叉树
// 两个条件同时成立，则为平衡二叉树
func IsBalanced_Solution(pRoot *TreeNode) bool {
	// write code here

	if pRoot == nil {
		return true
	}
	l := treeDepth(pRoot.Left)
	r := treeDepth(pRoot.Right)

	return math.Abs(float64(l-r)) <= 1 && IsBalanced_Solution(pRoot.Right) && IsBalanced_Solution(pRoot.Left)
}

func treeDepth(root *TreeNode) int {
	if root == nil {
		return 0
	}
	leftHeight := treeDepth(root.Left)
	rightGeight := treeDepth(root.Right)

	return max(leftHeight, rightGeight) + 1
}

func max(a, b int) int {
	if a >= b {
		return a
	}
	return b
}