从上到下打印二叉树

问题陈述

从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。

1
2
3
4
5
6
7
8
9
10
例如:
给定二叉树: [3,9,20,null,null,15,7],

​     3
​    / \
    9  20
​      / \
      15  7
返回：
[3,9,20,15,7]

思路分析

按层遍历输出的话可想到BFS（宽度优先遍历）。由此可用LinkedList结构的队列存储TreeNode，结点值存在ArrayList，然后以数组方式遍历输出。

具体步骤：

  • 若为空，直接返回一个空数组。

  • 根结点入队，根（首次为根，后续为队列下一结点）结点出队存入ArrayList，判断根结点的左右结点是否为空，不空则加入队列。这样不断入队出队，直到队列为空。

  • 以数组方式打印出ArrayList元素。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
public class BFS_printBT {
    public List<Integer> levelPrint(TreeNode root){
        List<Integer> list=new ArrayList<>();
        Queue<TreeNode> queue=new LinkedList<TreeNode>(){{add(root);}};
        while (!queue.isEmpty()){
            TreeNode node= queue.poll();
            list.add(node.val);
            if(node.left!=null) queue.offer(node.left);
            if(node.right!=null) queue.offer(node.right);
        }
        return 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
public class BFS_printBinaryTree {
    public int[] levelOrder(TreeNode root){
        if(root==null) return new int[0];
        Queue<TreeNode> queue=new LinkedList<TreeNode>() {{ add(root); }};
        ArrayList<Integer> ans=new ArrayList<>();
        while (!queue.isEmpty()){
            TreeNode node=queue.poll();
            ans.add(node.val);
            if(node.left!=null) queue.add(node.left);
            if(node.right!=null) queue.add(node.right);

        }
        int[] res=new int[ans.size()];
        for(int i=0;i<ans.size();i++){
            res[i]=ans.get(i);
            System.out.println(res[i]);
        }
        return res;
    }
    public static void main(String[] args){
        TreeNode root=new TreeNode(4);
        root.left=new TreeNode(3);
        root.right=new TreeNode(6);
        BFS_printBinaryTree bfs_printBinaryTree=new BFS_printBinaryTree();
        bfs_printBinaryTree.levelOrder(root);
    }
}

相关知识点

ArrayList和LinkedList比较

ArrayList

  • ArrayList是线性表（数组）
  • get（） 直接获取某个元素，复杂度为O(1)。
  • add（） 添加元素，复杂度O(1)。
  • add（index，e） 在第e个元素后加入元素，起后元素需要后移，复杂度为O(n)。
  • remove（） 删除元素，其后元素需要后移，复杂度为O(n)。

LinkedList

  • LinkedList是链表。
  • get（） 获取某个元素，依次遍历，复杂度为O(n)。
  • add（） 添加元素，复杂度O(1)。
  • add（index，e） 在第e个元素后加入元素，先查找到第e个元素，然后指针指向操作，整个过程复杂度为O(n)。
  • remove（） 删除元素，直接指针指向，复杂度为O(1)。

queue的remove（）和poll（）方法

  • Queue 中 remove() 和 poll() 都是用来从队列头部删除一个元素。
  • 在队列元素为空的情况下，remove() 方法会抛出NoSuchElementException异常，poll() 方法只会返回 null 。

实现打印每一层后换行输出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public List<List<Integer>> levelorder(TreeNode root){
    Queue<TreeNode> queue=new LinkedList<TreeNode>();
    List<List<Integer>> list=new ArrayList<>(); //{{3},{9,20},{15,7}}
    if(root!=null) queue.add(root);
    while(!queue.isEmpty()){
        List<Integer> tmp=new ArrayList<>();
        for(int i=queue.size();i>0;i--){ //初始化为当前queue的size，第一次size为1，第二次为2，第三次为2
            TreeNode node=queue.poll();
            tmp.add(node.val); //tmp添加node
            if(node.left!=null) queue.add(node.left);
            if(node.right!=null) queue.add(node.right);
        }
        list.add(tmp);
    }
    return list;
}

实现之字形打印

第一行从左到右打印，第二行从右到左打印，依次交替~

思路：BFS+双端队列。

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

另：反转 list 可直接用

Collections.reverse( list );