Tino又想吃肉了

判断平衡二叉树

Note swift algorithm leetcode tree
Word count: 390Reading time: 1 min
2021/03/25

递归分治思想判断平衡二叉树

给定一个二叉树，判断它是否是高度平衡的二叉树。

本题中，一棵高度平衡二叉树定义为：一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 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
class Solution {
    func isBalanced(_ root: TreeNode?) -> Bool {
        if(root == nil){
            return true
        }

        let lfs = deep(root?.left)
        let rfs = deep(root?.right)
        let cut = lfs - rfs
        if(cut > 1 || cut < -1){
            return false
        }else{
            let le = isBalanced(root?.left)
            let ri = isBalanced(root?.right)
            return le && ri
        }
    }

    func deep(_ root:TreeNode?) -> Int{
        guard let node = root else{ return 0}

        let lfs = deep(root?.left)
        let rhs = deep(root?.right)

        return lfs > rhs ? lfs+1 : rhs+1
    }
}

这是一种比较简洁的解决方案，通过deep函数计算左右子树的最大深度，并通过递归调用isBalanced判断子树是否也是平衡二叉树，若有一个子树不为平衡二叉树，那整个二叉树必然不为平衡二叉树。但算法的性能和效率有待改进，leetcode执行用时60ms，内存消耗14.8MB

其中，计算二叉树高度的代码需要加深理解，老是容易忘记比较简洁的写法。

1
2
3
4
5
6
7
8
func deep(_ root:TreeNode?) -> Int{
        guard let node = root else{ return 0}

        let lfs = deep(root?.left)
        let rhs = deep(root?.right)

        return lfs > rhs ? lfs+1 : rhs+1
    }

Tino Wu

CATALOG
  1. 1. 给定一个二叉树，判断它是否是高度平衡的二叉树。
    1. 1.1. 这是一种比较简洁的解决方案，通过deep函数计算左右子树的最大深度，并通过递归调用isBalanced判断子树是否也是平衡二叉树，若有一个子树不为平衡二叉树，那整个二叉树必然不为平衡二叉树。但算法的性能和效率有待改进，leetcode执行用时60ms，内存消耗14.8MB
Total : 35
2022
2021
swift iOS Tools algorithm leetcode tree 动态规划 计网 DFS算法 双指针 排序 BFS 性能优化 底层原理 操作系统 启动流程
Note