理论
前序、中序、后序主要根据遍历时根结点的顺序来决定。
- 前序遍历（根结点在前面）
先遍历根结点，然后遍历左子树，最后遍历右子树 - 中序遍历（根结点在中间）
先遍历左子树，再遍历根结点，最后遍历右子树 - 后序遍历（根结点在后面）
先遍历左子树，再遍历右子树，最后遍历根结点
理解
有一个二叉树如下图：
二叉树
- 前序遍历结果：ABCDEFGHIJ
- 中序遍历结果：CBEDFAHGIJ
- 后序遍历结果：CEFDBHJIGA
实战
- 前序递归遍历
from typing import List
class TreeNode:
def __init__(self, val='', left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def preorderTraversal(self, root: TreeNode) -> List[int]:
def preorder(root: TreeNode):
if not root:
return []
res.append(root.val)
preorder(root.left)
preorder(root.right)
res = []
preorder(root)
return res
e = TreeNode('e')
f = TreeNode('f')
d = TreeNode('d', e, f)
c = TreeNode('c')
b = TreeNode('b', c, d)
h = TreeNode('h')
j = TreeNode('j')
i = TreeNode('i', right=j)
g = TreeNode('g', h, i)
a = TreeNode('a', b, g)
solu = Solution()
res = solu.preorderTraversal(a)
print(res)
打印结果：
['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j']
- 中序递归遍历
from typing import List
class TreeNode:
def __init__(self, val='', left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def preorderTraversal(self, root: TreeNode) -> List[int]:
def preorder(root: TreeNode):
if not root:
return []
preorder(root.left)
res.append(root.val)
preorder(root.right)
res = []
preorder(root)
return res
e = TreeNode('e')
f = TreeNode('f')
d = TreeNode('d', e, f)
c = TreeNode('c')
b = TreeNode('b', c, d)
h = TreeNode('h')
j = TreeNode('j')
i = TreeNode('i', right=j)
g = TreeNode('g', h, i)
a = TreeNode('a', b, g)
solu = Solution()
res = solu.preorderTraversal(a)
print(res)
打印结果：
['c', 'b', 'e', 'd', 'f', 'a', 'h', 'g', 'i', 'j']
- 后序递归遍历
from typing import List
class TreeNode:
def __init__(self, val='', left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def preorderTraversal(self, root: TreeNode) -> List[int]:
def preorder(root: TreeNode):
if not root:
return []
preorder(root.left)
preorder(root.right)
res.append(root.val)
res = []
preorder(root)
return res
e = TreeNode('e')
f = TreeNode('f')
d = TreeNode('d', e, f)
c = TreeNode('c')
b = TreeNode('b', c, d)
h = TreeNode('h')
j = TreeNode('j')
i = TreeNode('i', right=j)
g = TreeNode('g', h, i)
a = TreeNode('a', b, g)
solu = Solution()
res = solu.preorderTraversal(a)
print(res)
打印结果：
['c', 'e', 'f', 'd', 'b', 'h', 'j', 'i', 'g', 'a']
