public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> allResults = new ArrayList<>();
    if (root == null) {
        return allResults;
    }
    // 初始化递归调用
    travel(root, 0, allResults);
    return allResults;
}

// DFS 模板
private void travel(TreeNode root, int level, List<List<Integer>> results) {
    // 终止条件
    if (results.size() == level) {
        results.add(new ArrayList<>());
    }
    // 处理逻辑
    results.get(level).add(root.val);
    
    // 向下递归
    if (root.left != null) {
        travel(root.left, level + 1, results);
    }
    if (root.right != null) {
        travel(root.right, level + 1, results);
    }
    // 状态恢复，清理临时变量等
}

public void dfs(TreeNode root) {
    // 记录节点是否访问
    Map<Integer, Integer> visited = new HashMap<>();

    if(root == null) {
        return ;
    }

    Stack<TreeNode> stack = new Stack<TreeNode>();
    stack.push(root);

    // 显式使用栈实现非递归
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        if(visited.containsKey(node.val)) {
            continue;
        } else {
            visited.put(node.val, 1);
        }

        for(int i=node.children.size()-1; i>=0; i--) {
            stack.push(node.children.get(i));
        }
    }

}

// 树节点定义
public class TreeNode { 
    int val;    
    TreeNode left;    
    TreeNode right;    
    TreeNode(int x) {
        val = x;
    }
}

// 树的按层次遍历(BFS)
public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> allResults = new ArrayList<>();
    if (root == null) {
        return (allResults);
    }
    Queue<TreeNode> nodes = new LinkedList<>();
    nodes.add(root);
    while (!nodes.isEmpty()) {
        // 记录本层次终止条件
        int size = nodes.size();
        List<Integer> results = new ArrayList<>();
        for (int i = 0; i < size; i++) {
            TreeNode node = nodes.poll();
            results.add(node.val);
            // 添加下一层次节点
            if (node.left != null) {
                nodes.add(node.left);
            }
            if (node.right != null) {
                nodes.add(node.right);
            }
        }
        allResults.add(results);
    }
    return (allResults);
}