400,二叉树的锯齿形层次遍历

400,二叉树的锯齿形层次遍历

I may not be able to change the past, but I can learn from it.

我也许不能改变过去发生的事情,但能向过去学习。

问题描述

今天来看一道比较简单的题,给定一个二叉树,返回其节点值的锯齿形层次遍历。(即先从左往右,再从右往左进行下一层遍历,以此类推,层与层之间交替进行)。

 

例如:

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

    3

   / \

  9  20

    /  \

   15   7

返回锯齿形层次遍历如下:

[

  [3],

  [20,9],

  [15,7]

]

 

BFS打印

二叉树的的层次遍历就是一层一层的遍历,也就是我们俗称的BFS(宽度优先搜索算法(又称广度优先搜索)),之前在373,数据结构-6,树中讲过树的宽度优先搜索,最简单的方式就是使用队列。但这题打印的时候多了一个条件,就是不能一直从一个方向打印,要先从左边打印然后再从右边打印……,就这样交替进行,所以这里要有个变量来判断是从左往右还是从右往左打印,代码比较简单,我们来看下。

 1public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
2    List<List<Integer>> res = new ArrayList<>();
3    if (root == null)
4        return res;
5    Queue<TreeNode> queue = new LinkedList<>();
6    queue.add(root);
7    boolean leftToRight = true;
8    while (!queue.isEmpty()) {
9        List<Integer> level = new ArrayList<>();
10        //统计这一行有多少个节点
11        int count = queue.size();
12        //遍历这一行的所有节点
13        for (int i = 0; i < count; i++) {
14            //poll移除队列头部元素(队列在头部移除,尾部添加)
15            TreeNode node = queue.poll();
16            //判断是从左往右打印还是从右往左打印。
17            if (leftToRight) {
18                level.add(node.val);
19            } else {
20                level.add(0, node.val);
21            }
22            //左右子节点如果不为空会被加入到队列中
23            if (node.left != null)
24                queue.add(node.left);
25            if (node.right != null)
26                queue.add(node.right);
27        }
28        res.add(level);
29        leftToRight = !leftToRight;
30    }
31    return res;
32}

上面代码中如果把第17-21行的代码直接换成第18行的代码就是我们之前讲过的BFS,就是一层一层往下打印。只不过这里多了一个条件的判断。

 

当然我们还可以根据每一层是第几层来判断,如果根节点是第1层的话,那么我们在层数是奇数的时候从左往右打印,如果层数是偶数的时候从右往左打印。在前面我们讲队列的时候359,数据结构-3,队列我们讲到了双端队列,就是一个可以在两边同时添加和删除的队列。这里我们使用上面两种方式的结合,来看下代码。

 1public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
2    List<List<Integer>> res = new ArrayList<>();
3    if (root == null)
4        return res;
5    //双端队列,两边都可以操作
6    Deque<TreeNode> deque = new LinkedList<>();
7    //添加到队列的头
8    deque.addFirst(root);
9    while (!deque.isEmpty()) {
10        List<Integer> level = new ArrayList<>();
11        //统计这一行有多少个节点
12        int count = deque.size();
13        //遍历这一行的所有节点
14        TreeNode cur;
15        for (int i = 0; i < count; i++) {
16            if (res.size() % 2 == 1) {
17                //从左边往右边打印
18                //移除队列头部的元素,如果子节点不为空加入到队列的尾部
19                cur = deque.removeFirst();
20                if (cur.right != null)
21                    deque.addLast(cur.right);
22                if (cur.left != null)
23                    deque.addLast(cur.left);
24            } else {
25                //从右边往左边打印
26                //移除队列尾部的元素,如果子节点不为空加入到队列的头部
27                cur = deque.removeLast();
28                if (cur.left != null)
29                    deque.addFirst(cur.left);
30                if (cur.right != null)
31                    deque.addFirst(cur.right);
32            }
33            level.add(cur.val);
34        }
35        res.add(level);
36    }
37    return res;
38}

 

DFS打印

这题除了使用BFS以外,我们还可以使用DFS。但这里我们要有个判断,如果走到下一层的时候集合没有创建,我们要先创建下一层的集合,代码也很简单,我们来看下。

 1public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
2    List<List<Integer>> res = new ArrayList<>();
3    travel(root, res, 0);
4    return res;
5}
6
7private void travel(TreeNode cur, List<List<Integer>> res, int level) {
8    if (cur == null)
9        return;
10    //如果res.size() <= level说明下一层的集合还没创建,所以要先创建下一层的集合
11    if (res.size() <= level) {
12        List<Integer> newLevel = new LinkedList<>();
13        res.add(newLevel);
14    }
15    //遍历到第几层我们就操作第几层的数据
16    List<Integer> list = res.get(level);
17    //这里默认根节点是第0层,偶数层相当于从左往右遍历,
18    // 所以要添加到集合的末尾,如果是奇数层相当于从右往左遍历,
19    // 要把数据添加到集合的开头
20    if (level % 2 == 0)
21        list.add(cur.val);
22    else
23        list.add(0, cur.val);
24    //分别遍历左右两个子节点,到下一层了,所以层数要加1
25    travel(cur.left, res, level + 1);
26    travel(cur.right, res, level + 1);
27}

 

总结

这题最简单的一种方式就是参照二叉树的BFS打印,然后稍作修改,如果当前行是从左往右打印,那么下一行就从右往左打印。如果当前行是从右往左打印,那么下一行就从左往右打印,代码基本上没什么难度。

 

 

400,二叉树的锯齿形层次遍历

399,从前序与中序遍历序列构造二叉树

388,先序遍历构造二叉树

373,数据结构-6,树

372,二叉树的最近公共祖先

 

 

400,二叉树的锯齿形层次遍历

长按上图,识别图中二维码之后即可关注。

 

如果喜欢这篇文章就点个"赞"吧

上一篇:js判断是否为闰年


下一篇:前端学习(3070):vue+element今日头条管理-删除文章400