二叉树的层序及Z形遍历

问题陈述

1、给你一个二叉树，请你返回其按 层序遍历和Z形遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。

示例：

二叉树：[3,9,20,null,null,15,7],

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
    3
   / \
  9  20
    /  \
   15   7
层序返回结果：
[
  [3],
  [9,20],
  [15,7]
]
Z形返回结果：
[
 [3],
 [20,9],
 [15,7],
]

层序遍历

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
class Solution{
    public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> res = new ArrayList<>();

    Queue<TreeNode> queue = new ArrayDeque<>();//双端队列
    if (root != null) {
        queue.add(root);
    }
    while (!queue.isEmpty()) {
        int n = queue.size();
        List<Integer> level = new ArrayList<>();
        for (int i = 0; i < n; i++) { 
            TreeNode node = queue.poll();
            level.add(node.val);
            if (node.left != null) {
                queue.add(node.left);
            }
            if (node.right != null) {
                queue.add(node.right);
            }
        }
        res.add(level);
        //res.add(0,level); 实现从最后一层开始打印。将每次的level放在第一位，之前在第一位的往后移。
    }

    return res;
 }
}

Z形遍历

1、解法一

和层次遍历一个模板，但是对层数多了一个奇偶判断，并对偶数层list进行反转。

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
class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
         List<List<Integer>> res = new ArrayList<>();
         Queue<TreeNode> queue = new ArrayDeque<>();
    if (root != null) {
        queue.add(root);
    }
    int count=1;
    while (!queue.isEmpty()) {
        int n = queue.size();
        List<Integer> level = new ArrayList<>();
        for (int i = 0; i < n; i++) { 
            TreeNode node = queue.poll();
            level.add(node.val);
            if (node.left != null) {
                queue.add(node.left);
            }
            if (node.right != null) {
                queue.add(node.right);
            }
        }
        if(count%2==0) Collections.reverse(level);//list反转
        count++;
        res.add(level);
    }

    return res;

    }
}

2、解法二

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class Z_printBinaryTree {
    public List<List<Integer>>  levelOrder(TreeNode root){
        Queue<TreeNode> queue=new LinkedList<>();
        List<List<Integer>> list=new ArrayList<>();
        if(root!=null) ((LinkedList<TreeNode>) queue).add(root);
        while (!queue.isEmpty()){
            LinkedList<Integer> tmp=new LinkedList<>();
            for(int i=0;i<queue.size();i--){
                TreeNode node=queue.poll();
                if(list.size()%2==0) tmp.addLast(node.val);
                else tmp.addFirst(node.val);
                if(node.left!=null) ((LinkedList<TreeNode>) queue).add(node.left);
                if(node.right!=null) ((LinkedList<TreeNode>) queue).add(node.right);

            }
            list.add(tmp);
        }
        return list;
    }