跳转至

树 Tree

树是有向无环图（directed acyclic graph），有n个节点和n-1个边。

遍历 Traversal

这里的order是对node来说的，如果node是最先访问的，就是pre-order，如果是中间访问的，就是in-order，如果是最后访问的，就是post-order。

  1. 前序（pre-order）：节点 → 左子树 → 右子树，NLR
  2. 中序（in-order）：左子树 → 节点 → 右子树，LNR
  3. 后序（post-order）：左子树 → 右子树 → 节点，LRN

颜色标记法-一种通用且简明的树遍历方法

只要会写前序的递归，另外两种的递归写法差不多。

前序递归（纯函数，dfs()的所有依赖都是以参数形式传进来的）。

class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        # 递归
        return dfs(root, [])

def dfs(root, resultList):
    return resultList + [root.val] + dfs(root.left, []) + dfs(root.right, []) if root else resultList

前序递归（直接处理scope内的变量ans）。

class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        # 递归
        ans = []
        def dfs(root):
            if root:
                ans.append(root.val)
                dfs(root.left)
                dfs(root.right)
        dfs(root)
        return ans

前序迭代（iterative），利用一个栈（stack，FIFO），一直向左到底。

class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        # 迭代
        ans, stack, node = [], [], root
        while stack or node:
            while node:
                ans.append(node.val)
                stack.append(node)
                node = node.left
            node = stack.pop()
            node = node.right
        return ans

前序迭代的另一种写法，更常规，更好理解，更推荐！

class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        # 迭代
        ans, stack = [], [root]
        while stack:
            node = stack.pop()
            if node:
                ans.append(node.val)
                stack.append(node.right)
                stack.append(node.left)
        return ans

中序递归，和前序几乎完全一样。

# 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]:
        # 递归，和前序差不多
        ans = []
        def inOrder(node):
            if node:
                inOrder(node.left)
                ans.append(node.val)
                inOrder(node.right)
        inOrder(root)
        return ans

广度优先搜索没有什么前中后序。

节点 → 所有子节点 → 子节点的子节点 → ……

LeetCode

# 题名 难度 标签 备注
144 Binary Tree Preorder Traversal 中等 DFS 简单基础题，不过要熟练掌握递归和迭代两种办法。