Python实现交替层序遍历二叉树的程序

假设我们有一个二叉树，我们需要交替地从左到右、从右到左显示每一层的节点值。

例如，输入：

则输出为：[5, -10, 4, -2, -7, 15]

为了解决这个问题，我们将遵循以下步骤：

  • 如果根节点为空，则

    • 返回一个新的列表

  • s1 := 初始包含根节点的列表

  • s2 := 一个新的列表

  • res := 一个新的列表

  • 当s1或s2不为空时，执行以下操作：

    • 当s1不为空时，执行以下操作：

      • node := 从s1删除最后一个元素

      • 如果node的左子节点不为空，则

        • 将node的左子节点添加到s2的末尾

      • 如果node的右子节点不为空，则

        • 将node的右子节点添加到s2的末尾

      • 将node的值添加到res的末尾

    • 当s2不为空时，执行以下操作：

      • node := 从s2删除最后一个元素

      • 如果node的右子节点不为空，则

        • 将node的右子节点添加到s1的末尾

      • 如果node的左子节点不为空，则

        • 将node的左子节点添加到s1的末尾

      • 将node的值添加到res的末尾

  • 返回res

让我们看下面的实现来更好地理解：

示例

在线演示

class TreeNode:
   def __init__(self, data, left = None, right = None):
      self.val = data
      self.left = left
      self.right = right

class Solution:
   def solve(self, root):
      if not root:
         return []
      s1 = [root]
      s2 = []
      res = []
      while s1 or s2:
         while s1:
            node = s1.pop()
            if node.left:
               s2.append(node.left)
            if node.right:
               s2.append(node.right)
            res.append(node.val)
         while s2:
            node = s2.pop()
            if node.right:
               s1.append(node.right)
            if node.left:
               s1.append(node.left)
            res.append(node.val)
      return res

ob = Solution()
root = TreeNode(5)
root.left = TreeNode(4)
root.right = TreeNode(-10)
root.left.left = TreeNode(-2)
root.right.left = TreeNode(-7)
root.right.right = TreeNode(15)
print(ob.solve(root))

输入

root = TreeNode(5)
root.left = TreeNode(4)
root.right = TreeNode(-10)
root.left.left = TreeNode(-2)
root.right.left = TreeNode(-7)
root.right.right = TreeNode(15)

输出

[5, -10, 4, -2, -7, 15]

更新于：2020年10月10日

101 次查看

开启你的职业生涯

完成课程获得认证

开始学习
广告