力扣第103题-二叉树的锯齿形层序遍历 前言 一、思路 二、

发表于

「这是我参与11月更文挑战的第22天，活动详情查看：2021最后一次更文挑战」

前言

力扣第103题 二叉树的锯齿形层序遍历 如下所示：

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

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

1
2
3
4
5
markdown复制代码    3
   / \
  9  20
    /  \
   15   7

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

1
2
3
4
5
csharp复制代码[
  [3],
  [20,9],
  [15,7]
]

一、思路

题目意思很简单,需要返回锯齿遍历的结果。

锯齿遍历是指从 第一层从右至左，第二层从左至右（根节点可忽略）。为了更好的理解这一行为，具体的路径如下图所示：

image.png

上图中 锯齿遍历 的结果为：[[1], [3,2],[4,5,6,7]]

这一题刚开始做的时候还是有点绕的，不过只要画个图模拟一下遍历的顺序就会清晰很多了。我们还是用上图中的树作为例子，用来分析。

在观察了第二层的节点遍历顺序和第三层节点的遍历顺序后，不难发现：当前层最先遍历到的节点的子节点，是下一层最后遍历的节点

例如第二层中的节点 3 是第二层最先遍历的。但是它的左右孩子子节点 6 和 7 是第三层最后面遍历的。

还有一点就是：在同一层中，如果当前层数是偶数，则右节点优先遍历。如果当前层数为奇数，则左节点优先遍历
（例如第三层中的 6 是要先于 7 遍历的）

综上所述，基于这种先进后出的结构，我们可以使用 栈 来保存遍历的节点，正好可以对应上当前层中先遍历，下一层中后遍历。

举个例子

我们以 [3,9,20,null,null,15,7] 来举例，重点讲述一下 栈 中存储元素

Deque<TreeNode> currentLevel：当前层节点

Deque<TreeNode> nextLevel：下一层节点

  1. 遍历 第一层 节点 [3]，先将它的左孩子 9 入栈，再将右孩子 20 入栈。nextLevel 栈中为 9 -> 20
  2. 遍历第二层，currentLevel 栈顶一直出栈。第一个节点为 20，将它的右孩子 7 入 nextLevel 栈，再将它的右孩子 15 入 nextLevel 栈。第二个节点为 9，没有左右孩子故不入栈。nextLevel 栈中为 7 -> 15
  3. 遍历第三层，currentLevel出栈。第一个节点为 15，第二个节点为 7，都没有左右孩子，故不入栈。
  4. 最终返回遍历的各节点值 [[3], [20, 9], [15, 7]] 即可

二、实现

实现代码

注意：因为考虑到不特殊处理根节点，所以我们认为根节点为第 0 层。所以奇偶性判断与思路中不是一致的

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
38
39
40
java复制代码    List<List<Integer>> ret = new ArrayList<>();

    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        if (root!=null) {
            Deque<TreeNode> stack = new LinkedList<>();
            stack.push(root);
            dfs(stack);
        }
        return ret;
    }

    public void dfs(Deque<TreeNode> currentLevel) {
        if (currentLevel.size() < 1)
            return;
        List<Integer> temp = new ArrayList<>();
        Deque<TreeNode> nextLevel = new LinkedList<>();
        // 遍历当前层级
        while (!currentLevel.isEmpty()){
            TreeNode treeNode = currentLevel.pop();
            temp.add(treeNode.val);
            // 因为需要添加下一层，所以是 size + 1
            if((ret.size() + 1) % 2 == 1) { // 奇数层：先加左边，再加右边
                if (treeNode.left != null){
                    nextLevel.push(treeNode.left);
                }
                if (treeNode.right != null){
                    nextLevel.push(treeNode.right);
                }
            } else {    // 偶数层：先加右边，再加左边
                if (treeNode.right != null){
                    nextLevel.push(treeNode.right);
                }
                if (treeNode.left != null){
                    nextLevel.push(treeNode.left);
                }
            }
        }
        ret.add(temp);
        dfs(nextLevel);
    }

测试代码

1
2
3
4
5
6
java复制代码public static void main(String[] args) {
    TreeNode treeNode = new TreeNode(1,
            new TreeNode(2,new TreeNode(4), null),
            new TreeNode(3, null, new TreeNode(5)));
    new Number103().zigzagLevelOrder(treeNode);
}

结果

image.png

三、总结

感谢看到最后，非常荣幸能够帮助到你~♥

如果你觉得我写的还不错的话，不妨给我点个赞吧！如有疑问，也可评论区见~

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%