先简单解释一下概念，标题中的「先中后」顺序主要是描述二叉树根与其子节点的相对访问顺序，也就是「先根，中根，后根」，即「根-左-右」，「左-根-右」, 「左-右-根」。
如果把上面的左-右互换，其实代码也只需要微调即可。
一. 首先还是先写下递归的解法
先序
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def preorderTraversal(self, root: TreeNode) -> List[int]:
if root is None:
return []
result = []
result.append(root.val)
result += self.preorderTraversal(root.left)
result += self.preorderTraversal(root.right)
return result
中序
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def inorderTraversal(self, root: TreeNode) -> List[int]:
result = []
if root is None:
return result
result += self.inorderTraversal(root.left)
result.append(root.val)
result += self.inorderTraversal(root.right)
return result
后序
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def postorderTraversal(self, root: TreeNode) -> List[int]:
result = []
if root is None:
return result
result += self.postorderTraversal(root.left)
result += self.postorderTraversal(root.right)
result.append(root.val)
return result
二. 使用栈加辅助节点的解法
用辅助节点p去扫描整颗树
先序
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def preorderTraversal(self, root: TreeNode) -> List[int]:
if root is None:
return []
result = []
stack = []
p = root
while p or len(stack):
if p:
stack.append(p)
result.append(p.val)
p = p.left
else:
p = stack[-1]
stack.pop()
p = p.right
return result
中序
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def inorderTraversal(self, root: TreeNode) -> List[int]:
result = []
if root is None:
return result
p = root
stack = []
while p or len(stack):
if p:
stack.append(p)
p = p.left
else:
p = stack[-1]
stack.pop()
result.append(p.val)
p = p.right
return result
后序，后序遍历要求左-右-根，这里借用先序的思路，先获得根-右-左的结果，然后将结果翻转一次得到左-右-根的结果
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def postorderTraversal(self, root: TreeNode) -> List[int]:
result = []
if root is None:
return result
stack = []
p = root
while p or len(stack):
if p:
stack.append(p)
result.append(p.val)
p = p.right
else:
p = stack.pop()
p = p.left
return result[::-1]
三. 其他解法
先序.
用根节点初始化栈，然后循环去判断栈是否为空。
弹出栈顶元素，将其值输出，并一次将其右-左子节点入栈。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def preorderTraversal(self, root: TreeNode) -> List[int]:
if root is None:
return []
result = []
stack = [root]
while len(stack):
p = stack.pop()
result.append(p.val)
if p.right:
stack.append(p.right)
if p.left:
stack.append(p.left)
return result
对应的还有后序遍历
同样是借鉴先序的经验，将左-右-根转化为根-右-左，然后来一次翻转得到左-右-根.
当然，翻转这个动作可以用另一个栈来实现，就不多说了。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def postorderTraversal(self, root: TreeNode) -> List[int]:
result = []
if root is None:
return result
stack = [root]
while len(stack):
p = stack.pop()
result.append(p.val)
if p.left:
stack.append(p.left)
if p.right:
stack.append(p.right)
return result[::-1]
后序遍历还有一种解法，用一个节点记录上一次访问的节点，这样只有当当前节点的左右子节点都为空或者上一次访问的节点为右子节点(右子节点存在)或左子节点（右子节点不存在)时，才被访问。这样就可以实现后序遍历。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def postorderTraversal(self, root: TreeNode) -> List[int]:
result = []
if root is None:
return result
stack = [root]
pre = root
p = root
while len(stack):
p = stack[-1]
if (p.left is None and p.right is None) or pre == p.left or pre ==p.right:
result.append(p.val)
stack.pop()
pre =p
else:
if p.right:
stack.append(p.right)
if p.left:
stack.append(p.left)
return result
后序好像还有双栈带标记的方法，就不去研究了。
还有一种使用Threaded binary tree的方法，留待后续了解。
想练手的可以参考Leetcode：
144. Binary Tree Preorder Traversal
94. Binary Tree Inorder Traversal
145. Binary Tree Postorder Traversal
网友评论