Python栈的应用：树的非递归遍历

2023-04-11 00:00:00 python 遍历递归

树的非递归遍历可以使用栈来实现，具体的实现方法如下:

建立一个栈，并将根节点入栈。
循环进行以下操作，直到栈为空：
弹出栈顶节点，并访问该节点。
如果该节点的右子节点不为空，将右子节点入栈。
如果该节点的左子节点不为空，将左子节点入栈。

以下是Python代码演示:

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def preorderTraversal(root: TreeNode) -> List[int]:
    if not root:
        return []
    stack, res = [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

def inorderTraversal(root: TreeNode) -> List[int]:
    if not root:
        return []
    stack, res = [], []
    node = root
    while stack or node:
        if node:
            stack.append(node)
            node = node.left
        else:
            node = stack.pop()
            res.append(node.val)
            node = node.right
    return res

def postorderTraversal(root: TreeNode) -> List[int]:
    if not root:
        return []
    stack, res = [root], []
    while stack:
        node = stack.pop()
        res.append(node.val)
        if node.left:
            stack.append(node.left)
        if node.right:
            stack.append(node.right)
    return res[::-1]

以上是前序、中序、后序非递归遍历的实现代码演示。如果想要测试，可以使用样例树，如下:

根据不同的遍历方式访问该树时，期望的输出如下:

前序遍历: [1, 2, 4, 5, 3, 6]
中序遍历: [4, 2, 5, 1, 3, 6]
后序遍历: [4, 5, 2, 6, 3, 1]

相关文章