【CT】LeetCode手撕—102. 二叉树的层序遍历

---

题目

• 原题连接：102. 二叉树的层序遍历

---

1-思路

• 1.借助队列 Queue ，每次利用 ①while 循环遍历当前层结点，②将当前层结点的下层结点放入 Queue中
• 2.每遍历一个结点，将值收集到 iterm 中，每一层遍历完，将结果存到 res 中

---

2- 实现

⭐102. 二叉树的层序遍历——题解思路

class Solution {
    // 结果
    List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> levelOrder(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        if(root==null){
            return res;
        }
        queue.offer(root);

        while(!queue.isEmpty()){
            int len = queue.size();
            List<Integer> iterm = new ArrayList<>();
            while(len>0){
                TreeNode node = queue.poll();
                iterm.add(node.val);
                if(node.left!=null){
                    queue.offer(node.left);
                }
                if(node.right!=null){
                    queue.offer(node.right);
                }
                len--;
            }
            res.add(new ArrayList(iterm));
        }
        return res;
    }
}
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

---

3- ACM实现

3-1 二叉树构造

public static TreeNode build(Integer[] nums){
    // 借助 queue 来实现二叉树构造
    Queue<TreeNode> queue = new LinkedList<>();
    TreeNode root = new TreeNode(nums[0]);
    queue.offer(root);
    int index = 1;
    while (!queue.isEmpty() && index < nums.length){
        TreeNode node = queue.poll();
        if(nums[index]!=null && index<nums.length){
            node.left = new TreeNode(nums[index]);
            queue.offer(node.left);
        }
        index++;
        if (nums[index]!=null && index<nums.length){
            node.right = new TreeNode(nums[index]);
            queue.offer(node.right);
        }
        index++;
    }
    return root;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

---

3-2 整体实现

public class levelTraversal {

    static class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(){}
        TreeNode(int x){
            val = x;
        }
    }

    public static TreeNode build(Integer[] nums){
        // 借助 queue 来实现二叉树构造
        Queue<TreeNode> queue = new LinkedList<>();
        TreeNode root = new TreeNode(nums[0]);
        queue.offer(root);
        int index = 1;
        while (!queue.isEmpty() && index < nums.length){
            TreeNode node = queue.poll();
            if(nums[index]!=null && index<nums.length){
                node.left = new TreeNode(nums[index]);
                queue.offer(node.left);
            }
            index++;
            if (nums[index]!=null && index<nums.length){
                node.right = new TreeNode(nums[index]);
                queue.offer(node.right);
            }
            index++;
        }
        return root;
    }


    static List<List<Integer>> res = new ArrayList<>();
    public static List<List<Integer>> levelOrder(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        if(root==null){
            return res;
        }
        queue.offer(root);

        while(!queue.isEmpty()){
            int len = queue.size();
            List<Integer> iterm = new ArrayList<>();
            while(len>0){
                TreeNode node = queue.poll();
                iterm.add(node.val);
                if(node.left!=null){
                    queue.offer(node.left);
                }
                if(node.right!=null){
                    queue.offer(node.right);
                }
                len--;
            }
            res.add(new ArrayList(iterm));
        }
        return res;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.println("输入二叉树构造数组");
        String input = sc.nextLine();
        input = input.replace("[","");
        input = input.replace("]","");
        String[] parts = input.split(",");
        Integer[] nums = new Integer[parts.length];
        for(int i = 0 ; i <parts.length;i++){
            if(!parts[i].equals("null")){
                nums[i] = Integer.parseInt(parts[i]);
            }else{
                nums[i] = null;
            }
        }
        TreeNode root = build(nums);

        List<List<Integer>> forRes = levelOrder(root);
        for(List<Integer> i:forRes){
            System.out.println(i.toString());
        }
    }

}

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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87