二叉树的通用遍历模板

遍历一棵二叉树，主要分为前序遍历、中序遍历和后序遍历三种方式，不同的方式输出的顺序不同：

前序遍历：根节点->左节点->右节点
中序遍历：左节点->根节点->右节点
后序遍历：左节点->右节点->根节点

本文将介绍递归、迭代、标记迭代以及莫里斯迭代四种方式的通用模板，对二叉树分别进行前中后序遍历，以及每种方式的特点。
首先先定义二叉树结构：

#定义二叉树类型
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

递归

递归是二叉树遍历中最简单的方式：

#前序遍历
def preorderTraversal(self, root: TreeNode) -> List[int]:
    res=[]
    def dfs(n):
        if not n:
            return
        res.append(n.val)
        dfs(n.left)
        dfs(n.right)
    dfs(root)
    return res

#中序遍历
def inorderTraversal(self, root: TreeNode) -> List[int]:
    res=[]
    def dfs(n):
        if not n:
            return
        dfs(n.left)
        res.append(n.val)
        dfs(n.right)
    dfs(root)
    return res

#后序遍历
def inorderTraversal(self, root: TreeNode) -> List[int]:
    res=[]
    def dfs(n):
        if not n:
            return
        dfs(n.left)
        dfs(n.right)
        res.append(n.val)
    dfs(root)
    return res

可以看到对于不同的遍历顺序，只需调整递归的顺序即可。
递归的时间复杂度是O(n) ，n为节点数，每个节点恰好访问一次。
空间复杂度是O(logn)，也就是树的高度。因为在递归过程中会用到logn的栈空间，如果一棵树所有节点都只有右节点或左节点，也就是说变成了一个链表，那么会用到O(n)的栈空间，所以在最坏情况下，空间复杂度是O(n)。

迭代

普通迭代的代码实现虽然不复杂，但却难以理解，它需要使用一个辅助栈来临时存储遍历的节点，遍历顺序为先找到最左节点，并将沿途遇到的节点全缓存进栈，然后从栈中依次弹出作为当前节点，然后再将该节点的右节点置为当前节点。

#中序遍历
def inorderTraversal(self, root: TreeNode) -> List[int]:
    res=[]
    stack=[]
    curr=root
    while curr or stack:
        while curr:
            stack.append(curr)
            curr=curr.left
        curr=stack.pop()
        res.append(curr.val)
        curr=curr.right
    return res

#前序遍历
def preorderTraversal(self, root: TreeNode) -> List[int]:
    res=[]
    stack=[]
    curr=root
    while curr or stack:
        while curr:
            res.append(curr.val)
            stack.append(curr)
            curr=curr.left
        curr=stack.pop()
        curr=curr.right
    return res

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

后序遍历这里用了点“作弊”的方式，修改了前序遍历的顺序（根-左-右），变成了（根-右-左），然后将结果逆序（左-右-根），并不是直接按后序顺序输出的。当然也有直接迭代的方法，不过实现起来很复杂，本文只想介绍一种通用模板，所以并没有深究。
迭代的时间复杂度也是O(n)，n为节点数。
空间复杂度是O(logn)，即树的高度，其辅助栈空间取决于树的结构，最坏情况会存储整棵树，即O(n)。

标记迭代

相较于普通迭代，标记迭代显得更容易理解，它除了在辅助栈中缓存节点外，还额外记录了这个节点的状态（0、1表示），0表示未访问，1表示已访问，第一次进栈的节点都是未访问状态，只有第二次进栈才会标记为已访问。
如果节点从栈中弹出的时候状态是0，那么就将它的左右节点继续入栈，同时将它本身的状态设置为1；如果节点从栈中弹出的时候状态是1，那么就将该节点打印出来。
进栈顺序决定了下次要访问的节点，也就决定了输出顺序，而只有当出栈的节点是已标记过的才会将其输出。

#中序遍历
def inorderTraversal(self, root: TreeNode) -> List[int]:
    res=[]
    stack=[(root,0)]
    while stack:
        n,s=stack.pop()
        if not n:
            continue
        if s==0:
            stack.append((n.right,0))
            stack.append((n,1))
            stack.append((n.left,0))
        else:
            res.append(n.val)
    return res

#前序遍历
def preorderTraversal(self, root: TreeNode) -> List[int]:
    res=[]
    stack=[(root,0)]
    while stack:
        n,s=stack.pop()
        if not n:
            continue
        if s==0:
            stack.append((n.right,0))
            stack.append((n.left,0))
            stack.append((n,1))
        else:
            res.append(n.val)
    return res

#后序遍历
def postorderTraversal(self, root: TreeNode) -> List[int]:
    res=[]
    stack=[(root,0)]
    while stack:
        n,s=stack.pop()
        if not n:
            continue
        if s==0:
            stack.append((n,1))
            stack.append((n.right,0))
            stack.append((n.left,0))
        else:
            res.append(n.val)
    return res

采用标记迭代，遍历三种顺序就和递归方式一样，代码几乎完全一样，只需更改顺序即可。
它的时间复杂度依然是O(n)，不过需要2倍的普通迭代的栈空间，空间复杂度依然可看作是O(logn)。

莫里斯(Morris)迭代

前面介绍的三种方式都需要使用额外的空间，而莫里斯迭代是一种采用时间换空间的方法，它并不需要额外的空间作为临时存储，不过代价就是每个节点可能会被访问2次。
其原理就是将每个节点的左子树的最右节点指向该节点本身，这样一来，相当于形成了一个环，当第二次再访问到该节点时，将关系断裂，恢复成二叉树原来的样子，其原理利用了二叉树中空节点的信息。

#中序遍历
def inorderTraversal(self, root: TreeNode) -> List[int]:
    res=[]
    while root:
        tail=root.left
        if tail:
            while tail.right and tail.right!=root:
                tail=tail.right
            if tail.right:         #tail.right==root
                res.append(root.val)
                tail.right=None
            else:                  #tail.right==None
                tail.right=root
                root=root.left
                continue
        else:
            res.append(root.val)
        root=root.right
    return res

#前序遍历
def preorderTraversal(self, root: TreeNode) -> List[int]:
    res=[]
    while root:
        tail=root.left
        if tail:
            while tail.right and tail.right!=root:
                tail=tail.right
            if tail.right:         #tail.right==root
                tail.right=None
            else:                  #tail.right==None
                res.append(root.val)
                tail.right=root
                root=root.left
                continue
        else:
            res.append(root.val)
        root=root.right
    return res

#后序遍历
def postorderTraversal(self, root: TreeNode) -> List[int]:
    res=[]
    while root:
        tail=root.right
        if tail:
            while tail.left and tail.left!=root:
                tail=tail.left
            if tail.left:         #tail.left==root
                tail.left=None
            else:                  #tail.left==None
                res.append(root.val)
                tail.left=root
                root=root.right
                continue
        else:
            res.append(root.val)
        root=root.left
    return res[::-1]