多节点树的层序遍历

1、多节点数

对于多节点树，顾名思义就是一个根节点下面有两个及两个以上的节点，对于多节点数的遍历，就无法使用二叉树的前中后序的遍历方式了。

2、具体思路

 对于上面的一个多节点树，我们想要层序遍历它，预期结果为：

第一层：1

第二层：2 3 4 5

第三层：6 7 8 9 10 11

所以一起的结果为：1 2 3 4 5 6 7 8 9 10 11

当然为了让显示的效果更加直观，我们可以随机将值打乱，这样可以更加直观的看到遍历的效果

2.1、逐层遍历（第一层）

直接遍历得到当前树的第一层的节点

root.val

2.2、逐层遍历（第二层......）

遍历第二层的数的节点

先得到当前节点的子节点

ListNode[] nodes = root.getChildren();

得到当前树的子节点的数组后，就可以对当前子节点数组进行遍历，然后递归去进行遍历当前子节点数组，直到叶子节点时结束

3、具体代码实现

package Leecode;
 
import java.util.ArrayList;
import java.util.List;
 
/**
 * 全都给我写代码
 *
 * @author jiangminghui
 * @date 2022/11/11 21:57
 **/
public class leetcode_429 {
    static List> list = new ArrayList<>();
    public static void main(String[] args) {
//        Node node1 = new Node();
//        node1.val = 1;
//        Node node2 = new Node();
//        node2.val = 2;
//        Node node3 = new Node();
//        node3.val = 3;
//        Node node4 = new Node();
//        node4.val = 4;
//        Node node5 = new Node();
//        node5.val = 5;
//        Node node6 = new Node();
//        node6.val = 6;
//        Node node7 = new Node();
//        node7.val = 7;
//        Node node8 = new Node();
//        node8.val = 8;
//        Node node9 = new Node();
//        node9.val = 9;
//        Node node10 = new Node();
//        node10.val = 10;
//        List children1 = new ArrayList<>();
//        children1.add(node2);
//        children1.add(node3);
//        children1.add(node4);
//        List children2 = new ArrayList<>();
//        children2.add(node5);
//        children2.add(node6);
//        children2.add(node7);
//        List children3 = new ArrayList<>();
//        children3.add(node8);
//        List children4 = new ArrayList<>();
//        children4.add(node9);
//        children4.add(node10);
//        node1.children = children1;
//        node3.children = children2;
//        node4.children = children3;
//        node8.children = children4;
        Node node1 = new Node();
        node1.val = 1;
        Node node2 = new Node();
        node2.val = 3;
        Node node3 = new Node();
        node3.val = 2;
        Node node4 = new Node();
        node4.val = 4;
        Node node5 = new Node();
        node5.val = 5;
        Node node6 = new Node();
        node6.val = 6;
        List children1 = new ArrayList<>();
        children1.add(node2);
        children1.add(node3);
        children1.add(node4);
        List children2 = new ArrayList<>();
        children2.add(node5);
        children2.add(node6);
        node1.children = children1;
        node2.children = children2;
        System.out.println(levelOrder(node1));
    }
    public static List> levelOrderNext(Node root) {
        if(root == null){
            return list;
        }
        List children = root.children;
        List innerList = new ArrayList<>();
        if(children!=null){
            for (int i = 0; i < children.size(); i++) {
                innerList.add(children.get(i).val);
            }
            list.add(innerList);
            for (int i = 0; i < children.size(); i++) {
                levelOrderNext(children.get(i));
            }
        }
        return list;
    }
    public static List> levelOrder(Node root){
        List arrayList = new ArrayList<>();
        arrayList.add(root.val);
        list.add(arrayList);
        List> listTemp = levelOrderNext(root);
        return listTemp;
    }
}