Python 中的 Zig-Zag 二叉树遍历

在本教程中，我们将了解如何解决二叉树的 Zig-Zag 层序遍历问题。

示例

我们有一个二叉树，如下所示：

我们将看到创建函数以打印给定二叉树的 Zig-Zag 遍历的不同方法。上述二叉树的 Zig-Zag 遍历将是 1 11 2 3 5 12 13 15 14 10 9 8 7 6 4

方法 - 1

解决此问题的第一个方法是使用两个栈。

我们将假定两个栈分别代表 current_level 和 next_level。我们还需要跟踪当前级别的 Zig-Zag 层序，即当前级别的遍历顺序是从左到右还是从右到左。我们将从 current_level 栈中弹出节点并打印这些节点的值。当当前级别的遍历顺序是从左到右时，我们将按从左到右的顺序压入节点。首先，我们将节点 node 的左子节点然后右子节点压入 next_level 栈。由于栈数据结构具有 LIFO（后进先出）的特性，当我们在下一个循环中弹出节点时，它们将按相反的顺序排列。

相反，当当前级别的遍历顺序是从右到左时，我们将按从右到左的顺序压入节点，即，首先是右子节点，然后在 next_level 栈中是左子节点。当到达级别末尾时，最后一步将是交换 current_level 和 next_level 栈。当 current_level 栈为空时，该级别将完成。

代码

输出

The zig-zag level order traversal of the binary tree is:
1 11 2 3 5 12 13  

时间复杂度：此算法的时间复杂度为 O(N)。我们使用线性循环遍历二叉树。

空间复杂度：此算法需要 O(N) 的额外内存空间，因此空间复杂度为 O(N)。我们使用了线性空间来存储栈。

方法 - 2

我们在上面的示例中使用了迭代方法来解决这个问题。这次我们将使用递归函数。该方法类似于另一个称为层序遍历的问题。这两个问题之间的唯一区别是我们必须创建一个额外的变量。该变量将跟踪从左到右和从右到左的顺序。

下面是用 Python 实现此方法的程序。

代码

输出

The Zig-Zag Level Order traversal of the given binary tree is:
1 11 2 3 5 12 13 15 14 10 9 8 7 6 4 

方法 - 3

下面是用 Python 实现此方法的程序。我们将使用队列数据结构。快速介绍一下，队列数据结构遵循 LIFO 原则，即后进先出。我们可以使用 collections 模块中的 deque 类来创建队列数据结构，或者我们可以创建一个 Python 列表并对列表应用 LIFO 原则。我们将根据遍历级别不同地使用 push 和 pop 命令。下面是此方法的实现。

代码

输出

The Zig-Zag Level Order traversal of the given binary tree is:
1 11 2 3 5 12 13 15 14 10 9 8 7 6 4

时间复杂度：此算法的时间复杂度为 O(N)。N 表示二叉树中存在的节点数。

辅助空间：队列数据结构占用 O(N) 空间；因此，此方法的空间复杂度为 O(N)。

方法 - 4

此方法将使用一种常见的算法，称为深度优先搜索 (DFS)。

下面是该程序的算法方法。

• 我们将通过定义一个 Python 函数来开始，该函数将以指向二叉树根节点的指针作为输入，并返回给定树的 Zig-Zag 层序遍历。
• 在此函数内部，我们将初始化一个空的 Python 列表。此列表将包含树中每个级别的节点。
• 我们将使用深度优先搜索算法执行一个修改版的二叉树前序遍历。要执行此方法，我们需要创建另一个函数，该函数将被递归调用。此递归函数将接收当前节点、该节点的级别以及 ans 数组。在此函数中，如果当前节点的级别大于或等于 ans 数组的长度，它将在 ans 数组中为当前节点的级别创建一个新数组，并将当前节点附加到此数组。否则，它将在 ans 数组中为当前输入级别的数组简单地附加当前节点。然后，此函数将首先在当前输入节点的左子树上递归调用，然后在右子树上递归调用。在调用这两个子树的函数时，我们将级别增加 1。
• 遍历完成后，我们将反转 ans 数组中奇数索引处的数组顺序。这些节点列表位于二叉树的奇数级别，需要遵循从右到左的顺序。这样，我们将获得 Zig-Zag 层序遍历。

下面是用 Python 代码展示如何实现此方法的代码。

代码

输出

The zig-zag level order traversal of the binary tree is:
1 11 2 3 5 12 13 

时间复杂度：此算法的时间复杂度为 O(N)。N 表示二叉树中存在的非空节点的总数。

辅助空间：此程序占用 O(H) 的额外内存空间。H 表示给定二叉树的高度。O(H) 的空间复杂度是因为我们将每个级别的节点值存储在不同的列表中。