用 Python 编写交替遍历二叉树的程序

pythonserver side programmingprogramming更新于 2026/1/19 8:44:17

假设我们有二叉树，我们必须通过从左到右和从右到左交替显示每个级别的值。

因此，如果输入如下

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

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

如果 root 为空，则
- 返回一个新的列表
s1 := 列表，最初插入根
s2 := 一个新列表
res := 一个新列表
当 s1 不为空或 s2 不为空时，执行
- 当 s1 不为空时，执行
  - 节点 := 从 s1 中删除最后一个元素
  - 如果节点左侧不为空，则
    - 在 s2 末尾插入节点左侧
  - 如果节点右侧不为空，则
    - 在末尾插入节点右侧s2 的
  - 在 res 末尾插入节点值
- 当 s2 不为空时，执行
  - 节点 := 从 s2 中删除最后一个元素
  - 如果节点右侧不为空，则
    - 在 s1 末尾插入节点右侧
  - 如果节点左侧不为空，则
    - 在 s1 末尾插入节点左侧
  - 在 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)