1. import java.util.*;
    3. /**
    4.  * Created by Intellij IDEA.
    5.  *
    6.  * @author JonnyJiang
    7.  * @date 2021/9/25
    8.  */
    9. public class NSubTree {
    10.     public Node root;
    13.     public List<Integer> dfs(){
    14.         return root.dfs(root);
    15.     }
    17.     public List<List<Integer>> bfs(){
    18.         return root.bfs(root);
    19.     }
    22.     public static void main(String[] args) {
    23.         NSubTree nSubTree = new NSubTree();
    27.         Node root = new Node(1);
    28.         Node sub1 = new Node(2);
    29.         Node sub2 = new Node(3);
    30.         Node sub3 = new Node(4);
    31.         Node sub4 = new Node(5);
    32.         Node sub5 = new Node(6);
    33.         Node sub6 = new Node(7);
    34.         Node sub7 = new Node(8);
    35.         Node sub8 = new Node(9);
    38.         List<Node> subs1 = new ArrayList<>();
    39.         subs1.add(sub1);
    40.         subs1.add(sub2);
    41.         subs1.add(sub3);
    45.         List<Node> subs2 = new ArrayList<>();
    46.         subs2.add(sub4);
    47.         subs2.add(sub5);
    49.         sub1.sub = subs2;
    51.         root.sub = subs1;
    54.         nSubTree.root = root;
    56.         System.out.println(nSubTree.bfs());
    60.     }
    62. }
    64. class Node{
    65.     public int val;
    66.     public List<Node> sub;
    68.     public Node(int val){
    69.         this.val = val;
    70.         sub = null;
    71.     }
    73.     public List<Integer> dfs(Node root) {
    74.         List<Integer> ret = new ArrayList<>();
    75.         if(root == null){
    76.             return ret;
    77.         }
    78.         if(root.sub == null){
    79.             ret.add(root.val);
    80.             return ret;
    81.         }
    83.         Stack<Node> stack = new Stack<>();
    84.         stack.push(root);
    85.         Node tmp;
    86.         while(!stack.isEmpty()){
    87.             tmp = stack.pop();
    88.             ret.add(tmp.val);
    89.             if(tmp.sub != null){
    90.                 Collections.reverse(tmp.sub);
    91.                 for(Node n:tmp.sub){
    92.                     stack.push(n);
    93.                 }
    94.             }
    95.         }
    97.         return ret;
    98.     }
    101.     public List<List<Integer>> bfs(Node root) {
    102.         List<List<Integer>> ret = new ArrayList<>();
    103.         if(root == null){
    104.             return ret;
    105.         }
    106.         if(root.sub == null){
    107.             List<Integer> e = new ArrayList<>();
    108.             e.add(root.val);
    109.             ret.add(e);
    110.             return ret;
    111.         }
    113.         Queue<Node> queue = new LinkedList<>();
    114.         Queue<Node> queue2 = new LinkedList<>();
    115.         queue.offer(root);
    117.         Node tmp;
    118.         List<Integer> list = new ArrayList<>();
    119.         ret.add(list);
    120.         while(!queue.isEmpty()){
    121.             tmp = queue.poll();
    122.             list.add(tmp.val);
    123.             if(tmp.sub != null){
    124.                 for(Node n:tmp.sub){
    125.                     queue2.offer(n);
    126.                 }
    127.             }
    128.             if(queue.isEmpty() && !queue2.isEmpty()){
    129.                 list = new ArrayList<>();
    130.                 ret.add(list);
    131.                 Queue<Node> t = queue2;
    132.                 queue2 = queue;
    133.                 queue = t;
    134.             }
    136.         }
    137.         return ret;
    138.     }
    141. }