大家好呀,我是 N 叉烧蛋。
之前的文章中我讲了二叉树的层次遍历,说了递归和非递归两种方法:
层次遍历就是表面意思,一层层的遍历,同一层的遍历按照从左到右逐个遍历。
今天来解决 N 叉树的层序遍历,不一样的叉,一样的套路,检查你之前学的是不是已经掌握了。
那下面我们就来搞搞这道题。
LeetCode 429:N 叉树的层序遍历
题意
给定一个 N 叉树,返回其节点值的层序遍历。
树的序列化输入是用层序遍历,没组子节点都由 null 值分隔。
示例
输入:root = [1,null,3,2,4,null,5,6]
输出:[[1],[3,2,4],[5,6]]
提示
- 树的高度不会超过 1000
- 树的节点总数在 [0,10^4] 之间
递归版
解析
我在【二叉树层次遍历】中说过,层次遍历使用递归法,有点反层次遍历的初衷。
层次遍历就是要一层一层的遍历,而我们都知道递归是一种解决到底然后再去解决其它问题的特点,也就是在深度。
使用递归法,就需要祭出递归的二步曲:
(1) 找出重复的子问题。
层次遍历是每一层的节点从左到右的遍历,所以在遍历的时候我们可以先遍历最左边的子树,再遍历靠左的子树,...,一直遍历完最右边的子树。
遍历的顺序是:1 -> 3 -> 5 -> 3 -> 6 -> 3 -> 1 -> 2 -> 1 -> 4。
# 递归处理子树 for child in root.children: self.level(child, depth+1, res)
需要注意的是,在遍历子树的时候,涉及到向上或者向下遍历,为了让递归的过程中的同一层的节点放在同一个列表中,在递归时要记录深度 depth。
同时,每次遍历到一个新的 depth,结果数组中没有对应的 depth 的列表时,在结果数组中创建一个新的列表保存该 depth 的节点。
# 若当前行对应的列表不存在,加一个空列表 if len(res) < depth: res.append([])
(2) 确定终止条件。
对于二叉树的遍历来说,想终止,即没东西遍历了,没东西遍历自然就停下来了。
即最下面一层的左右节点都为空了。
if root == None: return []
最重要的两步确定完了,那代码也就出来了。
二叉树层次遍历递归版,由于每个节点都被遍历到,所以时间复杂度为 O(n)。
此外在递归过程中调用了额外的栈空间,还维护了一个 res 的结果数组,所以空间复杂度为 O(n)。
代码实现
Python 代码实现
""" # Definition for a Node. class Node: def __init__(self, val=None, children=None): self.val = val self.children = children """ class Solution: def level(self,root: 'Node', depth, res): if root == None: return [] # 若当前行对应的列表不存在,加一个空列表 if len(res) < depth: res.append([]) # 将当前节点的值加入当前行的 res 中 res[depth - 1].append(root.val) # 递归处理子树 for child in root.children: self.level(child, depth+1, res) def levelOrder(self, root: 'Node') -> List[List[int]]: res = [] self.level(root, 1, res) return res
Java 代码实现
class Solution { private List<List<Integer>> res = new ArrayList<>(); private void level(Node root, int depth) { if (res.size() < depth) { res.add(new ArrayList<>()); } res.get(depth - 1).add(root.val); for (Node child : root.children) { level(child, depth + 1); } } public List<List<Integer>> levelOrder(Node root) { if (root != null){ level(root, 1); } return res; } }
非递归版
解析
由于层次遍历的属性非常契合队列的特点,所以非递归版的层次遍历用的是队列。
队列是一种先进先出(First in First Out)的数据结构,简称 FIFO。
如果不太了解队列的,可以看下面这篇文章:
思路很简单:
使用队列保存每一层的所有节点,把队列里的所有节点出队列,然后把这些出去节点各自的子节点入队列。
以此来完成对每层的遍历。
N 叉树的层次遍历非递归版,每个节点进出队列各一次,所以时间复杂度为 O(n)。
此外,额外维护了一个队列和一个结果数组,所以空间复杂度为 O(n)。
代码实现
Python 代码实现
class Solution: def levelOrder(self, root: 'Node') -> List[List[int]]: if root == None: return [] res = [] queue = [root] while queue: res.append([node.val for node in queue]) # 存储当前层的孩子节点列表 childNodes = [] for node in queue: # 若节点存在子节点,入队 if node.children: childNodes.extend(node.children) # 更新队列为下一层的节点,继续遍历 queue = childNodes return res
Java 代码实现
class Solution { public List<List<Integer>> levelOrder(Node root) { List<List<Integer>> res = new ArrayList<List<Integer>>(); if (root == null) { return res; } Queue<Node> queue = new LinkedList<Node>(); queue.offer(root); while (!queue.isEmpty()) { List<Integer> curlevel = new ArrayList<Integer>(); int curlevelLen = queue.size(); for (int i = 1; i <= curlevelLen; ++i) { Node node = queue.poll(); curlevel.add(node.val); queue.addAll(node.children); } res.add(curlevel); } return res; } }
图解 N 叉树的层序遍历到这就结束辣,你看我说的对吧,不管多数叉,不同的叉,一样的套路。
虽然 LeetCode 定义为难度中等的题,但是搞懂了原理,就和切水题一样简单。
还是那句话,只要大家认真去学,认真的思考,就一定能快乐的切题。
当然,也要记得点赞 + 在看 + 转发的三连,让我也快乐呀~
我是帅蛋,我们下次见!