本题要求判断一棵二叉树是否“平衡”:对树中每个节点,左、右子树的高度差的绝对值不超过 2。
高度定义:以“边数”为单位,单节点(无任何子节点)的高度为 0;空子树高度记为 0。
算法:采用后序遍历(DFS)自底向上计算。
lh、rh;abs(lh - rh) ≤ 2;若某处不满足则整棵树不平衡;max(lh, rh) + 1;小明是一位聪明的少年,他喜欢解答各种数学难题。一天,小明的老师给了他一个新的挑战:检查一棵二叉树是否是平衡树。二又树的节点和子节点的关系已经给出,小明需要判断树是否平衡——也就是每个节点的左右子树高度差的绝对值是否不超过 2 。
一个子树的高度定义为该子树的根节点到其所有子孙节点中最远的那一个节点的距离。树上两个节点的距离定义为两点间的边数。我们认为如果某个节点没有左儿子(右儿子)那么左子树(右子树)的高度为 0 。此外,如果一棵子树只有单独一个节点,那么该子树的高度也为 0 。
小明想要在老师面前证明自己,但有的题目实在有点人难了,请你帮帮他!