来，集中训练一下二叉树的层序遍历~

102.二叉树的层序遍历

https://leetcode.cn/problems/binary-tree-level-order-traversal/

迭代法

package tree;

import java.util.*;

/**
* 层序遍历
*/
public class LevelOrder {


    /**
    * 使用队列 先进先出
    */
    public List<List<Integer>> levelOrder(TreeNode root){
        ArrayList<List<Integer>> res = new ArrayList<>();
        if(root==null) return res;

        Queue<TreeNode> stack=new LinkedList<>();
        stack.offer(root);
        TreeNode cur;
        List<Integer> templist=new ArrayList<>();
        while(!stack.isEmpty()){
            int size = stack.size();
            templist = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                cur=stack.poll();
                templist.add(cur.val);
                if(cur.left!=null) stack.offer(cur.left);
                if(cur.right!=null) stack.offer(cur.right);
            }
            res.add(templist);
        }

        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
30
31
32
33
34
35
36
37

107.二叉树的层次遍历II

https://leetcode.cn/problems/binary-tree-level-order-traversal-ii/
与102的层序很像，只是将最后的数组翻转了一下

 public List<List<Integer>> level(TreeNode root){
        ArrayList<List<Integer>> res = new ArrayList<>();
        if(root==null) return res;

        Queue<TreeNode> queue=new LinkedList<>();
        queue.offer(root);
        TreeNode cur;
        ArrayList<Integer> tempList=new ArrayList<>();
        while(!queue.isEmpty()){
            int size = queue.size();
            tempList = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                cur = queue.poll();
                tempList.add(cur.val);
                if(cur.left!=null) queue.offer(cur.left);
                if(cur.right!=null) queue.offer(cur.right);
            }
            res.add(tempList);
        }
        Collections.reverse(res);
        return res;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

199.二叉树的右视图

https://leetcode.cn/problems/binary-tree-right-side-view/
同样也是使用队列进行处理

public List<Integer> q_199(TreeNode root){
        ArrayList<Integer> res = new ArrayList<>();
        if(root==null) return res;
        Queue<TreeNode> queue=new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){

            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode cur = queue.poll();
                if(i==size-1){
                    res.add(cur.val);
                }
                if(cur.left!=null) queue.offer(cur.left);
                if(cur.right!=null) queue.offer(cur.right);
            }
        }
        return res;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

637.二叉树的层平均值

https://leetcode.cn/problems/average-of-levels-in-binary-tree/

public List<Double> q_637(TreeNode root) {
        ArrayList<Double> res = new ArrayList<>();
        if (root == null)
            return res;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while(!queue.isEmpty())
        {
            int size = queue.size();
            double sum=0.0;
            for (int i = 0; i < size; i++) {
                TreeNode cur = queue.poll();
                sum+=cur.val;
                if (cur.left != null) queue.offer(cur.left);
                if (cur.right != null) queue.offer(cur.right);
            }
            res.add(sum/size);
        }
        return res;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

429.N叉树的层序遍历 (wrong)

https://leetcode.cn/problems/n-ary-tree-level-order-traversal/
实现：
也是类似于2叉树的层序遍历，使用队列，当队列非空的时候，先获取一开始队列的长度（相当于一层的节点数量），然后利用队列“先进先出”的特性，弹出队列中的头结点，加入临时数组，并将其子节点加入队列

public List<List<Integer>> q_429(Node root){
        ArrayList<List<Integer>> res = new ArrayList<>();

        if(root==null) return res;

        Queue<Node> queue=new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            int size = queue.size();
            ArrayList<Integer> tmpList = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                Node cur = queue.poll();
                tmpList.add(cur.val);
                if(cur.children!=null&&cur.children.size()!=0){
                    for (Node child : cur.children) {
                        queue.offer(child);
                    }
                }
            }
            res.add(tmpList);
        }
        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

515.在每个树行中找最大值

https://leetcode.cn/problems/find-largest-value-in-each-tree-row/

这里主要是结合获取最大值的方法

public List<Integer> q_515(TreeNode root){
        List<Integer> res=new ArrayList<>();
        if(root==null) return res;

        Queue<TreeNode> queue=new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            int size = queue.size();
            int max=Integer.MIN_VALUE;
            for (int i = 0; i < size; i++) {
                TreeNode cur = queue.poll();
                if(cur.left!=null) queue.offer(cur.left);
                if(cur.right!=null) queue.offer(cur.right);
                if(cur.val>max){
                    max=cur.val;
                }
            }
            res.add(max);
        }
        return res;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

116.填充每个节点的下一个右侧节点指针

https://leetcode.cn/problems/populating-next-right-pointers-in-each-node/

一般这种需要获取下一节点的问题，都需要先获取当前节点，和下一节点，并用变量存起来，然后再进行处理的

public Node q_116(Node root) {
        if(root==null) return null;

        Queue<Node> queue=new LinkedList<>();
        queue.offer(root);

        while(!queue.isEmpty()){
            int size = queue.size();

            Node cur = queue.poll();
            if(cur.left!=null) queue.offer(cur.left);
            if(cur.right !=null) queue.offer(cur.right);

            //之后再重新遍历一次,次数减少一次
            for (int i = 0; i < size - 1; i++) {
                Node next = queue.poll();
                if(next.left!=null) queue.offer(next.left);
                if(next.right!=null) queue.offer(next.right);

                cur.next=next;
                cur=next;
            }
        }

        return root;
    }
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

117.填充每个节点的下一个右侧节点指针II

https://leetcode.cn/problems/populating-next-right-pointers-in-each-node-ii/
解题思路：
这里利用是队列，以及第一层时队列的长度，然后获取每层第一个元素作为前节点，然后第二个元素作为后节点，之后再不断地交换，来设置元素的next节点
关键：前后节点变量的设置

public Node q_117(Node root){
        if(root==null) return null;

        Queue<Node> queue=new LinkedList<>();
        queue.offer(root);

        while(!queue.isEmpty()){
            int size = queue.size();
            Node pre=null;
            Node next=null;

            for (int i = 0; i <size; i++) {
                if(i==0){
                    pre = queue.poll();
                    if(pre.left!=null) queue.offer(pre.left);
                    if(pre.right !=null) queue.offer(pre.right);
                }else{
                    next = queue.poll();
                    pre.next= next;
                    pre=next;
                    if(next.left!=null) queue.offer(next.left);
                    if(next.right !=null) queue.offer(next.right);
                }

            }

        }
        return root;
    }
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

104.二叉树的最大深度

https://leetcode.cn/problems/maximum-depth-of-binary-tree/
解题思路：
同样是使用队列结合队列的长度进行处理，以及设置一个深度变量，在每层遍历的时候+1

 public int q_104(TreeNode root){
        if(root==null) return 0;
        Queue<TreeNode> queue=new LinkedList<>();

        queue.offer(root);
        int deep=0;
        while(!queue.isEmpty()){
            deep++;
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode cur = queue.poll();
                if(cur.left!=null) queue.offer(cur.left);
                if(cur.right !=null) queue.offer(cur.right);
            }
        }
        return deep;

    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

111.二叉树的最小深度

https://leetcode.cn/problems/minimum-depth-of-binary-tree/
解题思路：
先使用一个变量获取深度，然后当遍历的到某个节点的左孩子节点和右孩子节点都为空的时候，则返回该变量

public int q_111(TreeNode root) {
    if (root == null) return 0;
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    
    int deep = 0;
    while (!queue.isEmpty()) {
        deep++;
        int size = queue.size();
        for (int i = 0; i < size; i++) {
            TreeNode cur = queue.poll();
            
            //当左右节点都为空的时候，则代表时候最小长度了，否则还可以继续获取下去
            if(cur.left==null&&cur.right==null){
                return deep;
            }
            if (cur.left != null) {
                queue.offer(cur.left);
            }
            if (cur.right != null) {
                queue.offer(cur.right);
            }
            
        }
    }
    return deep;
    
    }
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

参考：代码随想录 https://www.programmercarl.com/
多谢carl哥！