剑指 Offer 55 - II. 平衡二叉树

easy

输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过 1，那么它就是一棵平衡二叉树。

后序遍历（DFS）

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
package tree

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

func abs(a int) int {
	if a < 0 {
		return -a
	}
	return a
}

func isBalanced(root *TreeNode) bool {
	var bp func(root *TreeNode) (int, bool)
	bp = func(root *TreeNode) (int, bool) {
        // 返回高度, 是否是平衡二叉树
		if root == nil {
			return 0, true
		}
		d1, b1 := bp(root.Left)
		d2, b2 := bp(root.Right)

		if b1 && b2 && abs(d1-d2) <= 1 {
			return max(d1, d2)+1, true
		}
		return max(d1, d2)+1, false
	}
	_, res := bp(root)
	return res

}