犹记得当年大二学习数据结构时，二叉树的迭代遍历就是书本中第一个难点

虽然认真看几遍标准代码能够理清逻辑和思路，但时隔多年，在leetcode上刷题时仍然不能由自己一遍写对

因此这里结合笔者的一些思考重新梳理一遍

理解二叉树的非递归遍历

树是一种数据结构，用于表示多个对象（结点/节点）间存在的层次关系

二叉树则是一种特殊情况，每个结点最多只有左右两棵子树，且必须区分子树的左右关系

树的遍历，是对树中的所有对象进行有损序列化（不保留结构信息，通常无法反序列化），以某种特定的顺序访问每个对象，且每个对象只被访问一次

注意，这里的顺序针对的是访问，而非发现，因为一个对象可以先被发现，等其他对象被访问后再访问该对象

笔者简单定义了以下两个行为

访问：获取对象上的某个值，在代码实现中通常就是打印出来或者存储到顺序容器上

发现：被某个变量存储或指向，因为树状结构不是数组，无法通过一个索引随机访问，初始时只有根节点被存储或指向

从存储结构的视角上看

对于链表，它是一个离散顺序结构，每次发现一个节点，访问其值后即可抛弃（使指针指向下一个节点），所以发现和访问是同时发生的（如果需要逆序访问一个链表，同样需要一个栈或者使用函数递归调用）

对于二叉树，可以认为是多分支的链表，我们每次发现一个节点，并不需要立即访问其值，也不能立刻抛弃它，因为节点指向左右两个分支，

按照不同的策略，存在不同的访问顺序，一些情况下发现与访问不是同时发生，我们必须使用一个容器暂存已发现的节点，可以是栈（三种遍历），也可以是队列（层序遍历）

访问顺序

• 从某个节点被发现时的视角看
  • 中序遍历：访问左子树->访问当前节点->访问右子树
  • 先序遍历：访问当前节点->访问左子树->访问右子树
  • 后序遍历：访问左子树->访问右子树->访问当前节点
  • 这是常见的三种模式，左右子树的顺序并不重要，通常先左后右，区别只在于当前节点在何时访问
• 从树状结构的全局视角看
  • 层序遍历：按节点的层次访问，相同层次内的节点顺序不作要求，一般按照整体结构的左右顺序

注意：借助函数的递归调用，我们可以很容易实现上面三种遍历，递归实现方式本质上利用了函数的调用栈结构对节点进行暂存

注意：上述的访问顺序针对的是每个结点，因此访问一个子树并不代表立刻访问子树的根节点，因为该子树的根节点也要符合这个访问顺序

注意：使用容器暂存的节点，只能说该节点已经被发现，在节点出栈时这个节点的状态是不确定的：节点已访问？左子树已访问？右子树已访问？这需要根据具体的代码上下文确定。这也说明了栈本身隐含了节点的特定状态。如果不保证栈中节点状态的一致性，往往需要额外的信息辅助判断，有时还需要二次入栈。

遍历与搜索的关系

搜索：一般发现结点的同时就进行访问，因为搜索的目标是找到符合特定要求的结点，对于访问的顺序没有特定要求，但仍然需要容器暂存结点，因为结点有多个分支。

对于二叉树，深度优先搜索和先序遍历的访问顺序一致，广度优先搜索和层次遍历的访问顺序一致

实现三种遍历

经典版本

先序

先序遍历时，结点本身先于左右子树访问

从这个角度看，可以发现时即刻访问，无需暂存结点

但由于存在左右子树分支，仍然需要暂存其中一个结点

def preorderTraversal(root):
    res = []
    stack = []
    node = root #当前处理的结点，这里就是“发现了”根节点
    while node != None or len(stack) > 0: #基本条件，有正在处理的结点或暂存区不为空
        # 阶段1：一发现就立刻访问，并且有左子树就一直进入左子树
        while node != None:
            res.append(node.val) #一发现就立刻访问
            stack.append(node) #因为要进入左子树，必须暂存结点，以便之后进入右子树
            node = node.left #“发现了”左子节点
        # 阶段2：从暂存区获取，进入右子树，因为之前进入暂存区时，左子树已访问过
        node = stack.pop() #出栈节点无用，其值入栈前已访问
        node = node.right #“发现了”右子节点
    return res

节点入栈之前，其值就已被访问

节点在出栈时，它的左子树已经被访问（因为左子树的结点总是比父节点后入栈）

事实上，由于入栈节点本身已被访问，可以仅入栈其右子结点，这样出栈后无需再跳转右子结点

中序

def inorderTraversal(root):
    res = []
    stack = []
    node = root
    while node != None or len(stack) > 0:
        # 阶段1：有左子树就一直进入左子树，发现但不访问，依次暂存父结点
        while node != None
            stack.append(node)
            node = node.left
        # 阶段2：从暂存区获取
        node = stack.pop()
        res.append(node.val) #出栈时才访问
        node = node.right 
    return res

节点在出栈时，它的左子树已经被访问（因为左子树的结点总是比父节点后入栈）

与先序版本的唯一不同是节点其值在出栈时才被访问，这样就实现了节点左子树先于节点本身访问

后序

后序遍历时，对于一个结点，必须其左右子树都访问后才能访问自身，而仅使用栈无法表示两种状态

• 左子树已访问右子树未访问
• 左右子树均已访问

需要额外的变量辅助判断

def postorderTraversal(root):
    res = []
    stack = []
    prev = None #上一个访问的节点
    node = root #当前处理的结点，这里就是“发现了”根节点
    while node != None or len(stack) > 0:
        while node != None: #直到一个节点没有左子树
            stack.append(node) #发现时并不访问，直接暂存 
            node = node.left
        node = stack.pop() #弹出的节点，要么没有左子树，要么左子树已访问过
        if not node.right or node.right == prev: #没有右或上一次访问就是右子树根节点
            res.append(node.val) #可以访问当前节点了
            prev = node
            node = None #注意，访问完需置空当前节点，因为本身和左右子树均已访问，该节点在下次循环不再使用
        else:
            stack.append(node) #放回！
            node = node.right #发现右子树
    return res

节点在出栈时

• 本身未被访问
• 节点左子树已经被访问（因为左子树的结点总是比父节点后入栈）
• 节点右子树是否访问是未知的，因此栈中的节点存在两种状态

需要维护一个变量prev记录上一次访问的结点

每次出栈一个结点

• 如果

  • prev就是出栈结点的右子结点，说明出栈结点右子树已访问完（因为右子结点是后序遍历右子树的最后一个结点）
  • 或者出栈结点没有右子树

  这两种情况都表示可以访问当前出栈节点

• 否则，应该将出栈节点放回栈中，进入该节点的右子树

prev变量区分了出栈节点的两种状态

经典版本（合并内外循环）

经典写法中，外部循环的条件为node != None or len(stack) > 0，内循环还有node != None的条件，初看时容易让人迷惑

可以将阶段一的循环并入外循环，在循环内部判断node != None，更加清晰

先序

def preorderTraversal(root):
    res = []
    stack = []
    node = root
    while node != None or len(stack) > 0:
        if node != None:
            res.append(node.val)
            stack.append(node)
            node = node.left
        else:
            node = stack.pop()
            node = node.right
    return res

中序

def inorderTraversal(root):
    res = []
    stack = []
    node = root
    while node != None or len(stack) > 0:
        if node != None:
            stack.append(node)
            node = node.left
        else:
            node = stack.pop()
            res.append(node.val)
            node = node.right
    return res

后序

def postorderTraversal(root):
    res = []
    stack = []
    prev = None
    node = root 
    while node != None or len(stack) > 0:
        if node != None:
            stack.append(node)
            node = node.left
        else:
            node = stack.pop()
            if not node.right or node.right == prev: 
                res.append(node.val)
                prev = node
                node = None
            else:
                stack.append(node)
                node = node.right
    return res

经典版本（改造）

在这个版本中，分离了 node != None 和 len(stack) > 0 这两个条件

以栈为中心，外循环保留 len(stack) > 0，每次取出一个节点

循环中每当访问一个节点，就一直进入左子树

中序

def inorderTraversal(root):
    res = []
    stack = []
    node = root
    while node != None:
        stack.append(node)
        node = node.left
    while len(stack) > 0:
        node = stack.pop()
        res.append(node.val)
        node = node.right
        while node != None:
            stack.append(node)
            node = node.left
    return res

后序

def postorderTraversal(root):
    res = []
    stack = []
    prev = None 
    if (root) stack.push(root)
    while len(stack) > 0:
        node = stack.pop()
        if not node.right or node.right == prev:
            res.append(node.val)
            prev = node
        else:
            stack.append(node)
            node = node.right
            while node != None: 
                stack.append(node)
                node = node.left
    return res

简化版本

根据三种遍历各自的特点，能进一步简化实现

先序

与经典实现不同，结点发现即入栈，而不是访问后跳转到子结点

所有节点都留到出栈时访问，因此无需判断node != None，所有node均由栈中获取

栈中节点状态保持一致性，均为已发现未访问

def preorderTraversal(root):
    res = []
    stack = []
    if root: stack.append(root)
    while len(stack) > 0: #暂存区不为空
        node = stack.pop()
        res.append(node.val) #出栈时访问，发现并暂存子节点
        if node.right: stack.append(node.right)
        if node.left: stack.append(node.left)
    return res

后序

由于有了pre信息，可以进一步简化

def postorderTraversal(root):
    res = []
    stack = []
    prev = None 
    if root: stack.append(root)
    while len(stack) > 0:
        node = stack.pop()
        if not node.right or node.right == prev:
            res.append(node.val)
            prev = node
        else:
            stack.append(node) #同样放回
            if node.right: stack.append(node.right)
            if node.left: stack.append(node.left)
    return res

统一写法

在这个版本中，为栈中节点多维护了一个状态变量，这样即使节点多次入栈，也能够区分不同状态的节点

当一个节点

• 第一次发现时被入栈，标记状态为FIND

• 第一次出栈时，按照不同遍历的特性依次入栈节点本身和左右子结点，标记左右子节点状态为FIND，而当前节点标记状态为VISIT

• 第二次出栈时，访问节点的值

为什么要再次入栈？因为中序和后序遍历时，节点发现时不能立刻被访问

FIND, VISIT = 0, 1
def traversal(root):
    res = []
    stack = [(FIND, root)]
    while len(stack) > 0:
        state, node = stack.pop()
        if state == FIND:
            # 只需改变这几行代码的顺序即可分别实现前中后序遍历，下面为中序遍历
            if node.right: stack.append((FIND, node.right))
            stack.append((VISIT, node))
            if node.left: stack.append((FIND, node.left))
        else:
            res.append(node.val)
    return res

如果觉得为每个节点维护一个状态浪费空间或者某些语言下实现不方便，可以仅标记某些少量的特殊状态，这里就是VISIT，简单的标记方法就是多向栈中加入一个空结点

def traversal(root):
    res = []
    stack = [root]
    while len(stack) > 0:
        node = stack.pop()
        if node != None: 
            # 只需改变这几行代码的顺序即可分别实现前中后序遍历，下面为中序遍历
            if node.right: stack.append(node.right)
            stack.append(node); stack.append(None) #多加入一个空结点以标记该节点下次出栈访问
            if node.left: stack.append(node.left)
        else: #遇到空结点说明需要再弹出一个节点，该节点是第二次出栈
            node = stack.pop()
            res.append(node.val)
    return res

实现层序遍历

层序遍历较简单，使用队列暂存一层的结点

依序访问一层的结点时，发现下一层的结点，依序入队列

def levelOrder(root):
    res = []
    queue = collections.deque([])
    if root: q.append(root)
    while queue:
        size = len(queue) #如果遍历结果不需要以层次分组，则无需设置内循环
        while size:
            node = queue.popleft()
            res.append(node.val)
            if node.left: queue.append(node.left)
            if node.right: queue.append(node.right)
            size -= 1
    return res

Mirros 遍历

这种方法可以在线性时间内，只占用常数空间来实现遍历，由 J. H. Morris 在 1979 年的论文「Traversing Binary Trees Simply and Cheaply」中首次提出，因此被称为 Morris 遍历。

线索二叉树

利用叶结点的空指针存储信息，无需栈

先序

def preorderTraversal(root):
    res = []
    pred = None #predecessor，左子树的最右下节点，中序遍历时当前节点的前驱节点
    while root:
        if root.left:
            pred = root.left
            while pred.right and pred.right != root:
                pred = pred.right
            if not pred.right:
                res.append(root.val) #访问当前节点
                pred.right = root # 让 pred 的右指针指向 root，这样之后的某次循环会回到root，走向if的另一个分支
                root = root.left #进入左子树
            else: # pred.right == root，说明左子树已经访问完了
                pred.right = None # 断开链接前驱和root的链接
                root = root.right 
        else:
            res.append(root.val)
            root = root.right
    return res

中序

def inorderTraversal(root):
    res = []
    pred = None #predecessor，左子树的最右下节点，中序遍历时当前节点的前驱节点
    while root:
        if root.left:
            pred = root.left
            while pred.right and pred.right !== root:
                pred = pred.right
            if not pred.right:
                pred.right = root # 让 pred 的右指针指向 root，这样之后的某次循环会回到root，走向if的另一个分支
                root = root.left
            else: # pred.right == root，说明左子树已经访问完了，可以访问root本身
                res.push(root.val)
                pred.right = null # 断开链接前驱和root的链接
                root = root.right 
        else: # 如果没有左孩子，则直接访问右孩子
            res.push(root.val)
            root = root.right
    return res

Morris 中序遍历的一个重要步骤就是寻找当前节点的前驱节点，并且 Morris 中序遍历寻找下一个点始终是通过转移到 right 指针指向的位置来完成的

• 如果当前节点没有左子树，则访问，然后跳转到当前节点的右子树
• 如果当前节点有左子树，那么它的前驱节点一定在左子树上，可以在左子树上一直向右前进，找到当前点的前驱节点
  • 如果前驱节点没有右子树（初始状态），就将前驱节点的 right 指针指向当前节点，这一步是为了在遍历完前驱节点后能找到前驱节点的后继，也就是当前节点
  • 如果前驱节点的右子树为当前节点，说明前驱节点已经被遍历过并被修改了 right 指针，这个时候重新将前驱的右子设置为空，访问当前节点，然后跳转到当前节点的右子树

附：N叉树遍历

N叉树遍历，相当于把树的孩子节点数量从两个拓展到了N个，此时一般不讨论 中序遍历（中间不唯一）

先序

def preorderTraversal(root):
    res = []
    stack = []
    if root: stack.append(root)
    while len(stack) > 0:
        node = stack.pop()
        res.append(node.val)
        for child in reversed(node.children): #将所有子结点逆序加入栈中
            stack.append(child)
    return res

后序

一种偷懒的实现方法是复用前序遍历的方法，然后对结果进行翻转，但这样并非真的“遍历”

下面仿照二叉树的后序遍历改造实现

def postorderTraversal(root):
    res = []
    stack = []
    pre = None; #记录上一个访问的节点
    if root: stack.append(root)
    while len(stack) > 0:
        node = stack[-1]
        #当前栈顶节点没有子节点 或 最后一个子节点已经访问过 则出栈 并加入记录
        if len(node.children) == 0 or node.children[-1] == pre:
            res.append(node.val)
            stack.pop()
            pre = node
        else: #否则 将全部子节点逆序加入栈中
            for child in reversed(node.children):
                stack.append(child)
    return res

层序

def levelOrder(root):
    res = []
    queue = collections.deque([])
    if root: queue.append(root)
    while queue:
        size = len(queue)
        while size:
            node = queue.popleft()
            res.append(node.val)
            for child in node.children:
                queue.append(child)
            size -= 1
    return res

相关题目

https://leetcode-cn.com/problems/binary-tree-inorder-traversal/

https://leetcode-cn.com/problems/binary-tree-preorder-traversal/

https://leetcode-cn.com/problems/binary-tree-postorder-traversal/

https://leetcode-cn.com/problems/binary-tree-level-order-traversal/

https://leetcode-cn.com/circle/article/ut9SBc/