遍历一棵二叉树，主要分为前序遍历、中序遍历和后序遍历三种方式，不同的方式输出的顺序不同：
- 前序遍历： 根节点->左节点->右节点
- 中序遍历： 左节点->根节点->右节点
- 后序遍历： 左节点->右节点->根节点
本文将介绍递归、迭代、标记迭代以及莫里斯迭代四种方式的通用模板，对二叉树分别进行前中后序遍历，以及每种方式的特点。 首先先定义二叉树结构：
123456 | #定义二叉树类型class TreeNode: def __init__(self, x): self.val = x self.left = None self.right = None |
|---|
递归
递归是二叉树遍历中最简单的方式：
1234567891011121314151617181920212223242526272829303132333435 | #前序遍历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)。
迭代
普通迭代的代码实现虽然不复杂，但却难以理解，它需要使用一个辅助栈来临时存储遍历的节点，遍历顺序为先找到最左节点，并将沿途遇到的节点全缓存进栈，然后从栈中依次弹出作为当前节点，然后再将该节点的右节点置为当前节点。
1234567891011121314151617181920212223242526272829303132333435363738394041 | #中序遍历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，那么就将该节点打印出来。 进栈顺序决定了下次要访问的节点，也就决定了输出顺序，而只有当出栈的节点是已标记过的才会将其输出。
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647 | #中序遍历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次。 其原理就是将每个节点的左子树的最右节点指向该节点本身，这样一来，相当于形成了一个环，当第二次再访问到该节点时，将关系断裂，恢复成二叉树原来的样子，其原理利用了二叉树中空节点的信息。
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859 | #中序遍历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] |
|---|
在莫里斯迭代中，后序遍历可看作是前序遍历的完整镜像，所有涉及到左右子节点的地方都进行互换，最后得到根-右-左的序列，再将结果集反转变成左-右-根的序列。 莫里斯迭代的所有左子节点会被访问2次，由于是常数，所以时间复杂度依然可看作是O(n)，但是它不借助任何额外空间，所以空间复杂度是O(1)。
