Iterative Postorder Traversals of Binary Tree

二叉树非递归后序遍历

1. Using 1 stack

O(n) time, O(n) space
初始设置栈为空,当前节点为根节点

执行以下操作,直到栈为空当前节点为空时停止:

  • 当前节点入栈,将左孩子设为当前节点,直到当前节点为空。
  • 令当前节点为stack[-1]
  • 如果当前节点右孩子为空,或等于prev(说明已经访问过右子树)
    – 访问当前节点,出栈
    – 设置prev=当前节点
    – 令当前节点=None
  • 否则,将右孩子设为当前节点
stack = []
node = root
while node and stack:
    if node:
        stack.append(node)
        node = node.left
    else:
        node = stack[-1]
        if not node.right or node.right == prev:
            print(node.val)
            stack.pop()
            node = None
        else:
            node = node.right

2. Using 2 stacks

O(n) time, O(n) space
stack: 用于储存和遍历子节点,初始化=[root]
path: 记录从根节点到当前节点的路径

执行以下操作,直到stack为空:

  • node = stack[-1]
  • 如果path栈顶元素不是node:
    – 当前节点,右孩子,左孩子(如果非空),依次入栈stack
  • 如果stack和path栈顶元素相同:
    – 访问node
    – stack和path弹出栈顶
stack = [root]
path = []
while stack:
    node = stack.pop()
    if path and path[-1] == node:
        path.pop()
        print(node.val)
    else:
        path.append(node)
        if node.right: stack.append(node.right)
        stack.append(node)
        if node.left: stack.append(node.left)

3. Using no stacks (Morris traversal)

O(n) time, O(1) space
在中序morris traversal的基础上作修改,遍历顺序由 “左根右” 变为 “左右根”。一种方法是添加dummy节点使得根节点为其左孩子,然后使用reverse辅助函数将每一层 “根到最右” 的部分反转,遍历该层之后再反转恢复结构。图片来源是leetcode用户xruzty这篇文章
Iterative Postorder Traversals of Binary Tree
新建dummy节点,设置其左孩子为root
初始化node = dummy
进行以下操作直到node为空:

  • 如果当前节点node的左孩子非空,找到中序遍历的前驱节点,左孩子的最右后代
    – 如果前驱节点的右孩子为空,将前驱节点的右孩子设置为当前节点。更新 node = node.left
    – 如果前驱节点的右孩子非空(则为当前节点;说明在上行过程中,前驱节点之前的层已被访问过):
    • 反转node.left至prev这一层
    • 遍历访问prev至node.left
    • 再次反转恢复原结构
    • 恢复树结构:prev.right = None
    • node = node.right
  • 如果node的左孩子为空,更新 node = node.right
def reverse(start, end):
    if start == end:
        return
    prev = start
    node = start.right
    while prev != to:
        tmp = node.right
        node.right = prev
        prev = node
        node = tmp


dummy = TreeNode(None)
dummy.left = root
node = dummy
while node and node.val:
    if node.left:
        prev = node.left
        while prev.right and prev.right != node:
            prev = prev.right
        if not prev.right:
            prev.right = node
            node = node.left
        else:
            reverse(node.left, prev)
            tmp = prev
            while tmp != node.left:
                print(tmp.val)
                tmp = tmp.right
            print(tmp.val)  # print node.left.val
            prev.right = None
            node = node.right
    else:
        node = node.right

参考资料:
https://leetcode.com/problems/binary-tree-postorder-traversal/discuss/45648/three-ways-of-iterative-postorder-traversing-easy-explanation

上一篇:PAT (Advanced Level) Practice 1086 Tree Traversals Again (25 分) 凌宸1642


下一篇:【剑指紫金港】1119 Pre- and Post-order Traversals 全网最易懂的非递归版