题目描述

给定一个 N 叉树，返回其节点值的_层序遍历_。（即从左到右，逐层遍历）。

树的序列化输入是用层序遍历，每组子节点都由 null 值分隔（参见示例）。

示例 1：

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

示例 2：

输入： root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
输出： [[1],[2,3,4,5],[6,7,8,9,10],[11,12,13],[14]]

提示：

• 树的高度不会超过 1000
• 树的节点总数在 [0, 10^4] 之间

---

代码

bfs

class Solution {  
    public List<List<Integer>> levelOrder(Node root) {  
        Queue<Node> queue = new LinkedList<>();  
        ArrayList<List<Integer>> lists = new ArrayList<>();  
        if (root == null) return lists;  
        lists.add(new ArrayList<Integer>(){{add(root.val);}});  
        for (Node child : root.children) {  
            queue.add(child);  
        }  
        while (!queue.isEmpty()) {  
            int len = queue.size();  
            ArrayList<Integer> temp = new ArrayList<>();  
            for (int i = 0; i < len; i++) {  
                Node poll = queue.poll();  
                temp.add(poll.val);  
                for (Node child : poll.children) {  
                    queue.add(child);  
                }  
            }  
            lists.add(temp);  
        }  
        return lists;  
    }  
}

dfs

class Solution {  
    List<List<Integer>> ans = new ArrayList<>();  
    public List<List<Integer>> levelOrder(Node root) {  
        dfs(root, 1);  
        return ans;  
    }  
    private void dfs(Node node, int deep) {  
        if (node == null) return;  
        if (ans.size() < deep) {  
            ans.add(new ArrayList<>());  
        }  
        ans.get(deep - 1).add(node.val);  
        for (Node child : node.children) {  
            dfs(child, deep + 1);  
        }  
    }  
}

---

题解

bfs

借助队列来完成bfs操作
先按顺序遍历一层的所有节点, 并把他们的所有子节点按顺序放入队列中
如此一轮遍历后, 队列就被存满了下一层的的节点存满了
如法炮制的多次循环把直到队列为空就得到答案了

dfs

用函数传递的参数表示当前栈的深度(从1开始)
应为深度也可以对应List下标, 所以很容易对对当前栈代表节点的值进行存储

---

具体代码参上

好的!本次分享到这就结束了
如果对铁汁你有帮助的话，记得点赞👍+收藏⭐️+关注➕
我在这先行拜谢了：）