二叉树、N叉树的层序遍历

柔情只为你懂 2022-12-13 01:39 186阅读 0赞

1、二叉树的层次遍历  
题目地址：[102. 二叉树的层序遍历][102.]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2phdmFfeHh4eA_size_16_color_FFFFFF_t_70_pic_center]

我们这里选择BFS(广度优先搜索)  
题目要求将二叉树的所有节点放入到一个列表中，然后列表中的每一个元素对应的是每一层的节点。

这里我们将每一层的节点取出来放入临时集合，然后再将临时集合作为一个元素放入最终的返回结果集合里

public static List<List<Integer>> levelOrder(BinaryTreeNode root){ 
            // 返回的结果集
            List<List<Integer>> lists = new ArrayList<>();
            if (null == root) { 
                return lists;
            }
            
            // 临时节点集合，其实是每一层的节点
            List<BinaryTreeNode> nodes = new ArrayList<>();
            nodes.add(root);
            while (!nodes.isEmpty()) { 
                int size = nodes.size();// 这个size是精髓，while中每一次循环就是每一层节点的数量
                // 临时结果集：其实是每一层的节点的值
                List<Integer> list = new ArrayList<>();
                for (int i = 0; i < size; i++) { 
                    // 每次都从该临时节点集合中移除第一个节点，并将该节点的值添加进临时结果集list
                    BinaryTreeNode remove = nodes.remove(0);
                    // 并将该节点的值添加进临时结果集list
                    list.add(remove.val);
                    
                    // 该节点的非空左、右节点分别放入临时节点集合(nodes)
                    if (null != remove.left) { 
                        nodes.add(remove.left);
                    }
                    if (null != remove.right) { 
                        nodes.add(remove.right);
                    }
                }
                // 每一层的节点值作为一个元素添加到最终返回结果中
                lists.add(list);
            }
            return lists;
        }

节点数据结构

* public class BinaryTreeNode { 
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) {  val = x; }
     * }

这里只是记录我自己的代码，以后有时间了，再进行优化，大家可以看leetCode里面有非常多的优质解答，还有很多bfs的模板什么的。

复杂度分析  
时间复杂度：O(n)O(n)。nn 指的是节点的数量。  
空间复杂度：O(n)O(n)，我们的列表包含所有节点。

2、N叉树的层次遍历  
题目地址：[429.N叉树的层次遍历][429.N]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2phdmFfeHh4eA_size_16_color_FFFFFF_t_70_pic_center 1]

思路都是一样的都是用BFS,只不过一个是二叉树，一个是多叉树而已，这里不在啰嗦，直接上代码

public static List<List<Integer>> levelOrder2 (NTreeNode root){ 
            List<List<Integer>> result = new ArrayList<>();
            if (null == root) { 
                return result;
            }
    
            // 临时队列其实就是每一层的节点
            Queue<NTreeNode> temp = new LinkedList();
            temp.offer(root);
            while (!temp.isEmpty()) { 
                // 当前层节点的数量
                int size = temp.size();
                List<Integer> levelOrderId = new ArrayList<>();
                for (int i = 0; i < size; i++) { 
                    NTreeNode poll = temp.poll();
                    // 将该节点移除，并加入当前层节点中
                    levelOrderId.add(poll.getVal());
                    // 这里将所有不为空的子节点全部放入temp临时队列里
                    List<NTreeNode> children = poll.getChildren();
                    if (null != children && 0 < children.size()) { 
                        temp.addAll(children);
                    }
                }
                // 将每一层节点当作一个元素加入最终返回结果里
                result.add(levelOrderId);
            }
            return result;
        }

节点数据结构

public class NTreeNode { 
        public int val;
        public List<NTreeNode> children;
        public NTreeNode(int val) { 
            this.val = val;
        }
        public int getVal() { 
            return val;
        }
        public void setVal(int val) { 
            this.val = val;
        }
        public List<NTreeNode> getChildren() { 
            return children;
        }
        public void setChildren(List<NTreeNode> children) { 
            this.children = children;
        }
    }

复杂度分析  
时间复杂度：O(n)O(n)。nn 指的是节点的数量。  
空间复杂度：O(n)O(n)，我们的列表包含所有节点。

[102.]: https://leetcode-cn.com/problems/binary-tree-level-order-traversal/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2phdmFfeHh4eA_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/00474c5fac314629ac2cab68e0e5f6f8.png
[429.N]: https://leetcode-cn.com/problems/n-ary-tree-level-order-traversal/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2phdmFfeHh4eA_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/b85cd6b9e03b4750897c6a921e7fe7a8.png