55-II.平衡二叉树

305 字

2 分钟

55-II.平衡二叉树

2022-03-23

2026-10-12

数据结构与算法

「剑指Offer」Swift

一、题目#

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

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

返回 true 。

示例 2:

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

返回 false 。

限制：

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

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/ping-heng-er-cha-shu-lcof

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

二、解法#

深度有用到上一题的思路。

1
func isBalanced(_ root: TreeNode?) -> Bool {
2
    let deepL = maxDepth(root?.left)
3
    let deepR = maxDepth(root?.right)
4
    if (deepL == 0 && deepR == 0) {
5
        return true
6
    }
7
    if (abs(deepL - deepR) > 1) {
8
        return false
9
    }
10
    return (isBalanced(root?.left) && isBalanced(root?.right))
11
}
12

13
func maxDepth(_ root: TreeNode?) -> Int {
14
    var deep = 0
15
    guard let root = root else { return deep }
16
    var queue: [TreeNode] = [root]
17
    var currentLevelCount = 1
18
    var nextLevelCount = 0
19

20
    while queue.isEmpty == false {
21
        let current = queue.removeFirst()
22
        currentLevelCount -= 1
23

24
        if let left = current.left {
25
            queue.append(left)
26
            nextLevelCount += 1
27
        }
28

29
        if let right = current.right {
30
            queue.append(right)
31
            nextLevelCount += 1
32
        }
33

34
        if currentLevelCount == 0 {
35
            deep += 1
36
            currentLevelCount = nextLevelCount
37
            nextLevelCount = 0
38
        }
39
    }
40

41
    return deep
42
}

一、 题目#

二、 解法#

一、题目#

二、解法#