leetcode刷题（81）——103. 二叉树的锯齿形层次遍历

老马的编程之旅

发布于 2022-06-22 13:53:34

2650

发布于 2022-06-22 13:53:34

给定一个二叉树，返回其节点值的锯齿形层次遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

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

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

[
  [3],
  [20,9],
  [15,7]
]

BFS（广度优先遍历）思路

最直观的方法是 BFS，逐层遍历树。

BFS 在每层的默认顺序是从左到右，因此需要调整 BFS 算法以生成锯齿序列。

最关键的是使用双端队列遍历，可以在队列的任一端插入元素。

如果需要 FIFO （先进先出）的顺序，则将新元素添加到队列尾部，后插入的元素就可以排在后面。如果需要 FILO （先进后出）的顺序，则将新元素添加到队列首部，后插入的元素就可以排在前面。

算法

实现 BFS 的几种算法。

使用两层嵌套循环。外层循环迭代树的层级，内层循环迭代每层上的节点。

也可以使用一层循环实现 BFS。将要访问的节点添加到队列中，使用分隔符（例如：空节点）把不同层的节点分隔开。分隔符表示一层结束和新一层开始。

这里采用第二种方法。在此算法的基础上，借助双端队列实现锯齿形顺序。在每一层，使用一个空的双端队列保存该层所有的节点。根据每一层的访问顺序，即从左到右或从右到左，决定从双端队列的哪一端插入节点。

实现从左到右的遍历顺序（FIFO）。将元素添加到队列尾部，保证后添加的节点后被访问。从上图中可以看出，输入序列 [1, 2, 3, 4, 5]，按照 FIFO 顺序得到输出序列为 [1, 2, 3, 4, 5]。

实现从右到左的遍历顺序（FILO）。将元素添加到队列头部，保证后添加的节点先被访问。输入序列 [1, 2, 3, 4, 5]，按照 FILO 顺序得到输出序列为 [5, 4, 3, 2, 1]。

class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
    if (root == null) {
            return new ArrayList<List<Integer>>();
        }
        boolean isleftToRight = true;
        List<List<Integer>> result = new ArrayList<>();
        LinkedList<Integer> level_list = new LinkedList<Integer>();
        LinkedList<TreeNode> nodeQueue = new LinkedList<>();
        nodeQueue.add(root);
        nodeQueue.add(null);
        while (!nodeQueue.isEmpty()) {
            TreeNode treeNode = nodeQueue.poll();
            if (treeNode != null) {
                if (treeNode.left != null) nodeQueue.add(treeNode.left);
                if (treeNode.right != null) nodeQueue.add(treeNode.right);
                if (isleftToRight) {
                    level_list.addLast(treeNode.val);
                } else {
                    level_list.addFirst(treeNode.val);
                }
            } else {
                result.add(level_list);
                level_list = new LinkedList<Integer>();
                if (nodeQueue.size() > 0)
                    nodeQueue.addLast(null);
                isleftToRight = !isleftToRight;
            }

        }
        return result;
    }
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2020-05-16，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法