Java 中二叉树的锯齿形遍历

二叉树的之字形遍历意味着对于顶层的节点，我们从左到右遍历；对于下一层，我们从右到左遍历；以此类推，我们不断地改变方向，从左到右，再从右到左。请注意，在顶层，我们可以选择从右到左遍历，然后下一层从左到右遍历。关于Java 中二叉树的之字形遍历，需要记住的关键点是，每一层的遍历方向都与前一层相反。在本教程中，我们将讨论实现二叉树之字形遍历的各种方法。请注意，每种方法都非常重要，尤其是在面试中。

对于下面的二叉树

之字形遍历是 18 30 20 60 34 45 65 41 71 59 31 82 98 50 12

或

之字形遍历是 18 20 30 65 45 34 60 12 50 98 82 31 59 71 41

方法 1：使用两个栈

可以使用两个栈实现二叉树的之字形遍历。将第一个栈视为当前层栈，第二个栈视为下一层栈。还需要一个变量来获取当前层顺序的信息（遍历是自右向左还是自左向右）。我们从 currentLevel 栈中弹出节点并显示节点值。当当前层的遍历方向是从左到右时，我们先将左子节点压入 nextLevel 栈，然后将右子节点压入。我们知道栈遵循后进先出 (LIFO) 原则。因此，下次从 nextLevel 栈中弹出节点时，遍历顺序将颠倒。同样，当遍历方向是从右到左时，我们先将右子节点压入，然后将当前节点的左子节点压入。请注意，在每一层的结束时（层结束意味着该层的所有节点都已遍历），我们必须交换栈，即 nextLevel 栈变成 currentLevel 栈，currentLevel 栈变成 nextLevel 栈。

实施

让我们来看一下使用两个栈实现二叉树之字形遍历的实现。

文件名： ZigZagTraversalExample.java

输出

The zigzag traversal of the binary tree is: 
18 30 20 60 34 45 65 41 71 59 31 82 98 50 12

时间复杂度：程序中只有一个 while 循环。因此，上述程序的time complexity 为 O(n)，其中 n 是二叉树中节点的总数。

空间复杂度：程序中有两个栈；每个栈的空间复杂度为 O(n)，其中 n 是二叉树中节点的总数。因此，O(n) + O(n) = O(2*n)，在渐近复杂度中等于 O(n)。

方法 2：使用双端队列 (Deque)

也可以使用双端队列实现二叉树的之字形遍历。需要注意的关键点是决定是从前端还是后端执行弹出操作。弹出操作决定了我们是从左到右还是从右到左遍历。

实施

让我们来看一下使用双端队列实现二叉树之字形遍历的实现。

文件名： ZigZagTraversalExample1.java

输出

The zigzag traversal of the binary tree is: 
18 30 20 60 34 45 65 41 71 59 31 82 98 50 12

时间复杂度：由于我们只访问一个节点一次；因此，上述程序的 time complexity 为 O(n)，其中 n 是二叉树中节点的总数。

空间复杂度：双端队列的最大大小可以达到 O((n + 1) / 2)，在渐近复杂度中等于 O(n)，其中 n 是二叉树中节点的总数。请注意，(n + 1) / 2 是满二叉树中的总叶节点数。

方法 3：使用递归

也可以使用递归来实现二叉树的之字形遍历。其思想是以不同的方式使用二叉树的层序遍历。遍历的方向将由一个在 0 和 1 之间切换的变量决定。请注意，该变量的值在完成每一层的遍历后会改变。

实施

让我们来看一下使用递归实现二叉树之字形遍历的实现。

文件名： ZigZagTraversalExample2.java

输出

The zigzag traversal of the binary tree is: 
18 30 20 60 34 45 65 41 71 59 31 82 98 50 12

时间复杂度：由于我们只访问一个节点一次；因此，上述程序的 time complexity 为 O(n)，其中 n 表示二叉树中节点的总数。

空间复杂度：上述程序的 space complexity 为 O(n)。

方法 4：使用栈和队列

在此方法中，我们进行层序遍历，但每一层的方向不同。在一层中，当从左到右遍历时，我们将所有遇到的节点添加到 array list *keep*。我们还将下一层的节点存储在栈中。当从右到左遍历时，我们从栈中弹出在上一步存储的节点。弹出的节点存储在 array list *keep* 中。最终返回 array list *keep*。请注意，此方法的优化是使用双端队列的方法。

实施

让我们来看一下使用栈和队列实现二叉树之字形遍历的实现。

文件名： ZigZagTraversalExample3.java

输出

The zigzag traversal of the binary tree is: 
18 30 20 60 34 45 65 41 71 59 31 82 98 50 12

时间复杂度：对于上述程序，time complexity 为 O(n)，其中 n 表示二叉树中节点的总数。

空间复杂度：上述程序的 space complexity 为 O(n)。