在Python中,可以使用列表(list)来实现顺序栈,因为列表支持动态数组,所以不会像固定大小的数组那样在栈满时无法添加元素。使用Python的内置函数`append()`和`pop()`可以实现压栈和弹栈操作。
下面是一个使用列表实现顺序栈的例子,以及如何使用它来遍历二叉树的中序遍历:
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def inorderTraversal(self, root: TreeNode):
if not root:
return []
stack = []
res = []
while stack or root:
if root:
stack.append(root)
root = root.left
else:
cur = stack.pop()
res.append(cur.val)
root = cur.right
return 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`作为栈来辅助进行中序遍历。遍历过程中,我们遵循左节点、根节点、右节点的顺序访问二叉树。