79.md

判断是不是平衡二叉树

题目

输入一棵节点数为 n 二叉树，判断该二叉树是否是平衡二叉树。 在这里，我们只需要考虑其平衡性，不需要考虑其是不是排序二叉树 平衡二叉树（Balanced Binary Tree），具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树

注：我们约定空树是平衡二叉树

示例

输入：{1,2,3,4,5,6,7}

返回值：true

思路

• 平衡二叉树是左子树的高度与右子树的高度差的绝对值小于等于1，同样左子树是平衡二叉树，右子树为平衡二叉树
• 利用后序遍历：左子树、右子树、根节点,可以先递归到叶子节点，然后在回溯的过程中来判断是否满足条件

实现

func IsBalanced_Solution(pRoot *TreeNode) bool {
	return postOrder(pRoot) != -1
}

func postOrder(root *TreeNode) int {
	if root == nil {
		return 0
	}
	// 如果不满足平衡二叉树的定义，则返回-1，并且如果左子树不满足条件了，直接返回-1，右子树也是如此，相当于剪枝，加速结束递归
	left := postOrder(root.Left)
	if left == -1 {
		return -1
	}
	right := postOrder(root.Right)
	if right == -1 {
		return -1
	}
	// 计算高差
	sub := 0
	max := 0
	if left > right {
		sub = left - right
		max = left
	} else {
		sub = right - left
		max = right
	}
	if sub > 1 {
		return -1
	}
	// 较长子树高度加上自己的高度
	return max + 1
}