理論

前序、中序、后序主要根據(jù)遍歷時(shí)根結(jié)點(diǎn)的順序來(lái)決定。

• 前序遍歷（根結(jié)點(diǎn)在前面）
  先遍歷根結(jié)點(diǎn)，然后遍歷左子樹，最后遍歷右子樹
• 中序遍歷（根結(jié)點(diǎn)在中間）
  先遍歷左子樹，再遍歷根結(jié)點(diǎn)，最后遍歷右子樹
• 后序遍歷（根結(jié)點(diǎn)在后面）
  先遍歷左子樹，再遍歷右子樹，最后遍歷根結(jié)點(diǎn)

理解

有一個(gè)二叉樹如下圖：

二叉樹

• 前序遍歷結(jié)果：ABCDEFGHIJ
• 中序遍歷結(jié)果：CBEDFAHGIJ
• 后序遍歷結(jié)果：CEFDBHJIGA

實(shí)戰(zhàn)

• 前序遞歸遍歷

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)

打印結(jié)果：

['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)

打印結(jié)果：

['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)

打印結(jié)果：

['c', 'e', 'f', 'd', 'b', 'h', 'j', 'i', 'g', 'a']