用 Python 编写程序对二叉树进行中序遍历

pythonserver side programmingprogramming更新于 2026/1/17 4:28:17

假设我们有一棵二叉树；我们必须找到一个包含根的中序遍历列表。我们知道中序遍历是一种遍历树中所有节点的方法，我们减去；

递归遍历左子树。
遍历当前节点。
递归遍历右子树。

我们必须尝试以迭代方式解决这个问题。

所以，如果输入是这样的

那么输出将是[12,13,4,16,7,14,22]

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

inorder := 一个新列表
stack := 一个空堆栈
无限地执行以下操作，执行
- 如果 root 不为空，则
  - 将 root 推入堆栈
  - root := root 的左侧
- 否则，当堆栈不为空时，则
  - root := 堆栈的顶部元素并从堆栈中弹出
  - 在末尾插入 root 的值有序
  - root := 根的右侧
- 否则，
  - 退出循环
return inorder

让我们看看下面的实现以便更好地理解 −

示例

class TreeNode:
   def __init__(self, value):
      self.val = value
      self.left = None
      self.right = None
class Solution:
   def solve(self, root):
      inorder = []
      stack = []
      while True:
         if root:
            stack.append(root)
            root = root.left
         elif stack:
            root = stack.pop()
            inorder.append(root.val)
            root = root.right
         else:
            break
      return inorder

ob = Solution()
root = TreeNode(13)
root.left = TreeNode(12)
root.right = TreeNode(14)
root.right.left = TreeNode(16)
root.right.right = TreeNode(22)
root.right.left.left = TreeNode(4)
root.right.left.right = TreeNode(7)
print(ob.solve(root))

输入

root = TreeNode(13)
root.left = TreeNode(12)
root.right = TreeNode(14)
root.right.left = TreeNode(16)
root.right.right = TreeNode(22)
root.right.left.left = TreeNode(4)
root.right.left.right = TreeNode(7)