110. 平衡二叉树

题目描述

给定一个二叉树，判断它是否是高度平衡的二叉树。本题中，一棵高度平衡二叉树定义为：

一个二叉树_每个节点_ 的左右两个子树的高度差的绝对值不超过 1 。

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：true

示例 2：

输入：root = [1,2,2,3,3,null,null,4,4]
输出：false

示例 3：

输入：root = [ ]
输出：true

解法一：自顶向下递归

 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
36
37


/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isBalanced(root *TreeNode) bool {
    if root == nil {
        return true
    }
    lHeight := height(root.Left)
    rHeight := height(root.Right)
    return abs(rHeight-lHeight) <= 1 && isBalanced(root.Left) && isBalanced(root.Right)
}

func height(root *TreeNode) int {
    if root == nil {
        return 0
    }
    return max(height(root.Left), height(root.Right)) + 1
}

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

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

解法二：自底向上递归

 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
36
37
38
39
40


/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isBalanced(root *TreeNode) bool {
    return height(root) != -1
}

func height(root *TreeNode) int {
    if root == nil {
        return 0
    }
    lHeight := height(root.Left)
    if lHeight == -1 {
        return -1
    }
    rHeight := height(root.Right)
    if rHeight == -1 || abs(rHeight-lHeight) > 1 {
        return -1
    }
    return max(lHeight, rHeight) + 1
}

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

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

优化上面的代码，上面的代码会把左子树的高度和右子树的高度都计算出之后才进行判断。优化方法如下：在计算出左子树的高度后判断左子树是否平衡，如果不平衡直接返回 -1，达到剪枝的目的。优化后的代码如下：

 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
36
37
38
39
40


/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isBalanced(root *TreeNode) bool {
    return height(root) != -1
}

func height(root *TreeNode) int {
    if root == nil {
        return 0
    }
    lHeight := height(root.Left)
    if lHeight == -1 {
        return -1
    }
    rHeight := height(root.Right)
    if rHeight == -1 || abs(rHeight-lHeight) > 1 {
        return -1
    }
    return max(lHeight, rHeight) + 1
}

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

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