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

题目描述

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

示例 1:

给定二叉树 [3,9,20,null,null,15,7]

返回 true 。

示例 2:

给定二叉树 [1,2,2,3,3,null,null,4,4]

返回 false 。

限制：

0 <= 树的结点个数 <= 10000

注意：本题与主站 110 题相同：https://leetcode-cn.com/problems/balanced-binary-tree/

解法一：递归（自顶向下）

 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


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

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

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

func max (x, y int) int {
    if x > y {
        return x
    }
    return y
}

解法二：递归（自底向上）

 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


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

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

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

func max(x, y int) int {
    if x > y {
        return x
    }
    return y
}