ACM 选手图解 LeetCode N 叉树的最大深度

简介: ACM 选手图解 LeetCode N 叉树的最大深度

大家好,我是深水炸蛋。


上篇文章解决了【二叉树的最大深度】,那今天就来多解决几个叉,搞一下 N 叉树的最大深度


如果你仔细看过我在二叉树的最大深度中的讲解,这道题对你来说没有难度。


为啥这么说呢?因为这本质上就是一类题。N 叉本就包含着二叉,解题的套路都是一样的。


那为啥还要再搞下这道题?我就是想看看有没有人没学废,抓出来打屁股

640.png


   LeetCode 559:N 叉树的最大深度


题意


给定一个 N 叉树,找到其最大深度。


最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。


示例


输入:root = [1,null,3,2,4,null,5,6]

输出:3

640.png


提示


  • 树的深度不超过 1000。
  • 树的节点数目位于 [0, 10^4] 之间。


题目解析


难度简单,求树的深度的通用题目。


还是那句话,你想了解这道题的做法,你得先搞明白 3 个概念:深度、高度、层次。


二叉树的深度是从根节点开始算起,依次往下是深度 1、2、...可以理解成一口井,从上往下看,也就是自顶向下看


二叉树的高度是从叶子节点算起,叶子节点高度是 1,依次往上类推可以看成是高楼,从下往上看,也就是自底向上看


二叉树的层次是从根节点算起,根节点是第一层,依次往下类推。


此外深度、高度、层次之间有如下关系:


二叉树的深度和层次是完全对应的,最大深度为最大层次数。二叉树的深度和高度正好相反


根据这 3 个概念,对应出解决 N 叉树最大深度的 3 个解题方法:


(1) 自顶向下


自顶向下,就是从根节点递归到叶子节点,计算这一条路径上的深度,并更新维护最大深度。


这个是正儿八经的求深度。每次先维护根节点的深度,再递归所有的子树

640.png


(2) 自底向上


自底向上,从叶子节点开始,一层一层的向上,最终汇集在根节点。


这种求的其实是 N 叉树的高度。递归的遍历各个子树的最大高度,比出最大的高度 maxChildHeight,加上根节点的高度 1,即为当前 N 叉树的最大高度。


因为 N 叉树的最大高度 = 最大深度,所以即可求出 N 叉树的最大深度。

640.png


(3) 自左向右


自左向右,就是从根节点开始,一层一层的遍历 N 叉树。


这种求的是 N 叉树的层次。N 叉树的最大层次就是其最大深度。


可以看出,这种一层一层的遍历,其实用的就是层次遍历

640.png



递归法


递归法,我以自底向上方式为例,解决本题,相比而言,对于递归法来说,这个方式更好理解。


递归法,按照套路我们要祭出递归二步曲:


(1) 找出重复的子问题。


这个问题很简单,找出子树的最大高度。同样对于各个子树来说,也都是同样的操作。

# 递归计算各个子树的高度
for child in root.children:
    maxChildHeight = max(maxChildHeight, self.maxDepth(child))

其实就是下面这张图的样子:


640.png



(2) 确定终止条件。


对于 N 叉树来说,想终止,即没东西遍历了,没东西遍历自然就停下来了。


那就是当前的节点是空的,既然是空的那就没啥好遍历。

# 节点为空,高度为 0
if root == None:
    return 0

Python 代码实现


"""
# Definition for a Node.
class Node:
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children
"""
class Solution:
    def maxDepth(self, root: 'Node') -> int:
        # 节点为空,高度为 0
        if root == None:
            return 0
        # 记录子树的最大高度
        maxChildHeight = 0
        # 递归计算各个子树的高度
        for child in root.children:
            maxChildHeight = max(maxChildHeight, self.maxDepth(child))
        # N 叉树的最大高度 = 子树的最大高度 + 1(1 是根节点)
        return maxChildHeight + 1


Java 代码实现


/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> children;
    public Node() {}
    public Node(int _val) {
        val = _val;
    }
    public Node(int _val, List<Node> _children) {
        val = _val;
        children = _children;
    }
};
*/
class Solution {
    public int maxDepth(Node root) {
        // 节点为空,高度为 0
        if(root == null){
            return 0;
        }
        // 记录子树的最大高度
        int maxChildHeight = 0;
        // 递归计算各个子树的高度
        for(Node child : root.children){
            maxChildHeight = Math.max(maxChildHeight, maxDepth(child));
        }
        // N 叉树的最大高度 = 子树的最大高度 + 1(1 是根节点)
        return maxChildHeight + 1;
    }
}


本题解,在递归过程中每个节点都被遍历到,时间复杂度为 O(n)


此外在递归过程中调用了额外的栈空间,栈的大小取决于 N 叉树的高度,N 叉树最坏情况下的高度为 n,所以空间复杂度为 O(n)


非递归法(迭代)


迭代法,我以自左向右,即层次遍历的方式为例。


我之前详细的写过层次遍历,不清楚层次遍历的小宝贝可以去看下:


ACM 选手带你玩转二叉树层次遍历(递归 + 非递归)


我在文章中讲过,非递归版的层次遍历用的则是队列,这是由于层次遍历的属性非常契合队列的特点。


具体做法就是:使用队列保存每一层的所有节点,把队列里的所有节点出队列,然后把这些出去节点各自的子节点入队列。用 depth 维护每一层。


比如对于下图:


640.png


首先初始化队列 queue 和层次 depth,将根节点入队列:

640.png

# 初始化队列和层次
queue = [root]
depth = 0

640.png当队列不为空,出队列,将所有的子节点入队列。640.png

640.png


# 当队列不为空
while queue:
    # 当前层的节点数
    n = len(queue)
    # 弹出当前层的所有节点,并将所有子节点入队列
    for i in range(n):
        node = queue.pop(0)
        for child in node.children:
            queue.append(child)
    depth += 1


下面就是按照上面的方式,出队列,入队列,维护当前层次,直至队列为空。

640.png


Python 代码实现

"""
# Definition for a Node.
class Node:
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children
"""
class Solution:
    def maxDepth(self, root: 'Node') -> int:
        # 空树,高度为 0
        if root == None:
            return 0
        # 初始化队列和层次
        queue = [root]
        depth = 0
        # 当队列不为空
        while queue:
            # 当前层的节点数
            n = len(queue)
            # 弹出当前层的所有节点,并将所有子节点入队列
            for i in range(n):
                node = queue.pop(0)
                for child in node.children:
                    queue.append(child)
            depth += 1
        # N 叉树最大层次即为 N 叉树最大深度
        return depth

Java 代码实现

class Solution {
    public int maxDepth(Node root) {
        // 节点为空,高度为 0
        if(root == null){
            return 0;
        }
        // 初始化队列和层次
        Queue<Node> queue = new LinkedList<>();
        queue.offer(root);
        int depth = 0;
        // 当队列不为空
        while(!queue.isEmpty()){
            // 当前层的节点数
            int n = queue.size();
            // 弹出当前层的所有节点,并将所有子节点入队列
            for(int i = 0; i < n; i++){
                Node node = queue.poll();
                for(Node child : node.children){
                    queue.offer(child);
                }
            }
            depth++;
        }
        // N 叉树最大层次即为 N 叉树最深深度
        return depth;
    }
}

本题解,对于每个节点,各进出队列一次,所以时间复杂度为 O(n)


此外,额外维护了一个队列,所以空间复杂度为 O(n)


图解 N 叉树的最大深度到这就结束辣,没骗你们吧?就是和在解决二叉树的最大深度用的是一个套路。


N 叉树的最大深度可以看成是一个求树的最大深度的标准模板,毕竟这个搞会了,以后什么二叉树三叉树四叉树...都就会了。


多做题多思考多积累,慢慢自己”蛋“药库的武器就会越来越多,最终由量变到质变。


如果认可,记得帮我点赞 + 在看 + 转发,让我看到你!


我是帅蛋,我们下次见啦!

相关文章
|
7天前
|
算法 数据可视化 数据挖掘
LeetCode题目104: 二叉树的最大深度(递归\迭代\层序遍历\尾递归优化\分治法实现 )
LeetCode题目104: 二叉树的最大深度(递归\迭代\层序遍历\尾递归优化\分治法实现 )
LeetCode题目104: 二叉树的最大深度(递归\迭代\层序遍历\尾递归优化\分治法实现 )
|
7天前
|
SQL 算法 数据可视化
LeetCode题目99:图解中叙遍历、Morris遍历实现恢复二叉树搜索树【python】
LeetCode题目99:图解中叙遍历、Morris遍历实现恢复二叉树搜索树【python】
|
7天前
|
存储 SQL 算法
LeetCode题目100:递归、迭代、dfs使用栈多种算法图解相同的树
LeetCode题目100:递归、迭代、dfs使用栈多种算法图解相同的树
|
7天前
|
存储 算法 数据可视化
python多种算法对比图解实现 验证二叉树搜索树【力扣98】
python多种算法对比图解实现 验证二叉树搜索树【力扣98】
|
12天前
|
搜索推荐 Java
单源最短路(只有一个起点)bfs,多源BFS,目录力扣675.为高尔夫比赛砍树,多源最短路问题:力扣542.01矩阵力扣1020.飞地的数量
单源最短路(只有一个起点)bfs,多源BFS,目录力扣675.为高尔夫比赛砍树,多源最短路问题:力扣542.01矩阵力扣1020.飞地的数量
|
12天前
|
算法 Java Go
【经典算法】LeetCode 100. 相同的树(Java/C/Python3/Go实现含注释说明,Easy)
【经典算法】LeetCode 100. 相同的树(Java/C/Python3/Go实现含注释说明,Easy)
5 0
|
20天前
|
算法 C语言 容器
从C语言到C++_25(树的十道OJ题)力扣:606+102+107+236+426+105+106+144+94+145(下)
从C语言到C++_25(树的十道OJ题)力扣:606+102+107+236+426+105+106+144+94+145
31 7
|
20天前
|
C语言
从C语言到C++_25(树的十道OJ题)力扣:606+102+107+236+426+105+106+144+94+145(中)
从C语言到C++_25(树的十道OJ题)力扣:606+102+107+236+426+105+106+144+94+145
25 1
|
20天前
|
算法 C语言 C++
从C语言到C++_25(树的十道OJ题)力扣:606+102+107+236+426+105+106+144+94+145(上)
从C语言到C++_25(树的十道OJ题)力扣:606+102+107+236+426+105+106+144+94+145
17 1
|
21天前
【力扣刷题】二叉树的中序遍历、二叉树的最大深度、翻转二叉树、对称二叉树
【力扣刷题】二叉树的中序遍历、二叉树的最大深度、翻转二叉树、对称二叉树
22 0