[LeetCode] 二叉树的层序遍历

题目：给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。

力扣链接：102. 二叉树的层序遍历 - 力扣（LeetCode）

思路：队列先进先出，符合一层一层遍历的逻辑，而用栈先进后出适合模拟深度优先遍历也就是递归的逻辑。

解答：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
/**
 * 迭代方式
 */
//保存最终返回结果
public List<List<Integer>> res = new ArrayList<>();
public List<List<Integer>> levelOrder(TreeNode root) {
    if (root == null) {
        return res;
    }
    
    //使用队列
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);
    
    while (!queue.isEmpty()) {
            //BFS打印，levelSize为每层的节点数
            int levelSize = queue.size();
            //保存每层的的节点值
            List<Integer> subList = new ArrayList<>();
        
            for (int i = 0; i < levelSize; i++) {
                //出队
                TreeNode treeNode = queue.poll();
                subList.add(treeNode.val);
                
                //当前节点的子节点入队
                if (treeNode.left != null) {
                    queue.add(treeNode.left);
                }
                if (treeNode.right != null) {
                    queue.add(treeNode.right);
                }
            }

            res.add(subList);
        }

        return res;
}

/**
 * 递归方式
 */
//保存最终返回结果
public List<List<Integer>> resList = new ArrayList<List<Integer>>();

public List<List<Integer>> levelOrder(TreeNode root) {
    bfs(root, 0);

    return  resList;
}

public void bfs(TreeNode node, Integer deep) {
    if (node == null) return;
    deep++;

    if (resList.size() < deep) {
        List<Integer> item = new ArrayList<>();
        resList.add(item);
    }
    resList.get(deep - 1).add(node.val);

    bfs(node.left, deep);
    bfs(node.right, deep);
}