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

package main

import (
	. "nc_tools"
)

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

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param pRoot TreeNode类
 * @return bool布尔型
 */
func IsBalanced_Solution(pRoot *TreeNode) bool {
	// write code here
	var checkTreeBalanced func(node *TreeNode) (int, bool)
	checkTreeBalanced = func(node *TreeNode) (int, bool) {
		if node == nil {
			return 0, true
		}
		leftHeight, leftBalance := checkTreeBalanced(node.Left)
		if !leftBalance {
			return 0, false
		}
		rightHeight, rightBalance := checkTreeBalanced(node.Right)
		if !rightBalance {
			return 0, false
		}
		if abs(leftHeight-rightHeight) > 1 {
			return 0, false
		}
		return max(leftHeight, rightHeight) + 1, true
	}
	_, check := checkTreeBalanced(pRoot)
	return check
}

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
}