Python栈的应用：二叉树的前序遍历、中序遍历和后序遍历

2023-04-10 00:00:00 python 二叉树 遍历

二叉树的前序遍历、中序遍历和后序遍历都可以使用栈来实现。栈的作用在于存储遍历时暂时不需要处理的节点，以便后续处理。

下面分别介绍三种遍历的实现方法：

  1. 前序遍历

前序遍历顺序为“根节点 -> 左子树 -> 右子树”，可以使用一个栈来辅助遍历。首先将根节点压入栈中，然后循环进行以下操作：

1.1 弹出栈顶元素，并将该节点的值添加到遍历结果中。

1.2 如果该节点存在右子树，将右子树压入栈中。

1.3 如果该节点存在左子树，将左子树压入栈中。

示例代码：

class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        res = []
        stack = []
        if root:
            stack.append(root)
        while stack:
            node = stack.pop()
            res.append(node.val)
            if node.right:
                stack.append(node.right)
            if node.left:
                stack.append(node.left)
        return res
  1. 中序遍历

中序遍历顺序为“左子树 -> 根节点 -> 右子树”，同样可以使用一个栈来辅助遍历。首先将所有左子节点压入栈中，然后循环进行以下操作：

2.1 弹出栈顶元素，并将该节点的值添加到遍历结果中。

2.2 如果该节点存在右子树，将右子树的全部左子节点压入栈中。

示例代码：

class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        res = []
        stack = []
        node = root
        while node or stack:
            while node:
                stack.append(node)
                node = node.left
            node = stack.pop()
            res.append(node.val)
            node = node.right
        return res
  1. 后序遍历

后序遍历顺序为“左子树 -> 右子树 -> 根节点”，难度较大但同样可以使用栈来实现。需要两个栈来辅助遍历。首先将根节点压入第一个栈中，然后循环进行以下操作：

3.1 弹出第一个栈顶元素，并将该节点的值添加到遍历结果中。

3.2 将该节点的左子树和右子树分别压入第一个栈中。

3.3 循环第一个栈直到为空，此时第二个栈中就存储了后序遍历的结果。

示例代码：

class Solution:
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        res = []
        stack1 = []
        stack2 = []
        if root:
            stack1.append(root)
        while stack1:
            node = stack1.pop()
            stack2.append(node)
            if node.left:
                stack1.append(node.left)
            if node.right:
                stack1.append(node.right)
        while stack2:
            res.append(stack2.pop().val)
        return res

以上是对栈在二叉树遍历中的应用的介绍和示例代码演示。

相关文章