在Python中,可以使用列表(list)来实现顺序栈,因为列表支持动态数组,所以不会像固定大小的数组那样在栈满时无法添加元素。使用Python的内置函数`append()`和`pop()`可以实现压栈和弹栈操作。
下面是一个使用列表实现顺序栈的例子,以及如何使用它来遍历二叉树的中序遍历:
class TreeNode:def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = rightclass Solution:def inorderTraversal(self, root: TreeNode):if not root:return []stack = []res = []while stack or root:if root:stack.append(root)root = root.leftelse:cur = stack.pop()res.append(cur.val)root = cur.rightreturn res创建一个二叉树node = TreeNode(1)node.left = TreeNode(2)node.right = TreeNode(3)创建一个Solution对象a = Solution()执行中序遍历b = a.inorderTraversal(node)print(b) 输出应该是 [2, 1, 3]
在这个例子中,`inorderTraversal`方法使用了一个列表`stack`作为栈来辅助进行中序遍历。遍历过程中,我们遵循左节点、根节点、右节点的顺序访问二叉树。

