树（Tree）结构题目分类与详解

树（Tree） 是算法面试中非常核心的数据结构，广泛涉及遍历、递归、DFS/BFS、二叉搜索树（BST）、平衡树、字典树（Trie）等知识点。本文将对树类常见题型进行系统分类与经典题目解析，帮助你快速掌握解题思路。

---

一、树的遍历（前序、中序、后序、层序）

1. 递归遍历

🧭 144. 二叉树的前序遍历

python
def preorderTraversal(root):
    res = []
    def dfs(node):
        if not node: return
        res.append(node.val)  # 前序
        dfs(node.left)
        dfs(node.right)
    dfs(root)
    return res

🌀 94. 二叉树的中序遍历

python
def inorderTraversal(root):
    res = []
    def dfs(node):
        if not node: return
        dfs(node.left)
        res.append(node.val)  # 中序
        dfs(node.right)
    dfs(root)
    return res

2. 迭代遍历（栈实现）

🧱 145. 二叉树的后序遍历

python
def postorderTraversal(root):
    res = []
    stack = []
    prev = None
    while root or stack:
        while root:
            stack.append(root)
            root = root.left
        root = stack[-1]
        if not root.right or root.right == prev:
            res.append(root.val)
            stack.pop()
            prev = root
            root = None
        else:
            root = root.right
    return res

3. 层序遍历（BFS）

🌳 102. 二叉树的层序遍历

python
def levelOrder(root):
    if not root: return []
    queue = collections.deque([root])
    res = []
    while queue:
        level = []
        for _ in range(len(queue)):
            node = queue.popleft()
            level.append(node.val)
            if node.left: queue.append(node.left)
            if node.right: queue.append(node.right)
        res.append(level)
    return res

---

二、二叉树递归问题

1. 树的深度与高度

📏 104. 二叉树的最大深度

python
def maxDepth(root):
    if not root: return 0
    return 1 + max(maxDepth(root.left), maxDepth(root.right))

⚖️ 110. 平衡二叉树

python
def isBalanced(root):
    def height(node):
        if not node: return 0
        left = height(node.left)
        right = height(node.right)
        if left == -1 or right == -1 or abs(left - right) > 1:
            return -1
        return 1 + max(left, right)
    return height(root) != -1

2. 路径问题

🛤️ 112. 路径总和

python
def hasPathSum(root, targetSum):
    if not root: return False
    if not root.left and not root.right:
        return targetSum == root.val
    return hasPathSum(root.left, targetSum - root.val) or \
           hasPathSum(root.right, targetSum - root.val)

🎯 437. 路径总和 III

python
def pathSum(root, targetSum):
    from collections import defaultdict
    prefix = defaultdict(int)
    prefix[0] = 1
    def dfs(node, curr_sum):
        if not node: return 0
        curr_sum += node.val
        res = prefix[curr_sum - targetSum]
        prefix[curr_sum] += 1
        res += dfs(node.left, curr_sum) + dfs(node.right, curr_sum)
        prefix[curr_sum] -= 1
        return res
    return dfs(root, 0)

---

三、二叉搜索树（BST）

1. BST性质验证

🔍 98. 验证二叉搜索树

python
def isValidBST(root):
    def helper(node, lower=float('-inf'), upper=float('inf')):
        if not node: return True
        if node.val <= lower or node.val >= upper:
            return False
        return helper(node.left, lower, node.val) and \
               helper(node.right, node.val, upper)
    return helper(root)

2. BST操作

➕ 701. 插入操作

python
def insertIntoBST(root, val):
    if not root: return TreeNode(val)
    if val < root.val:
        root.left = insertIntoBST(root.left, val)
    else:
        root.right = insertIntoBST(root.right, val)
    return root

➖ 450. 删除节点

python
def deleteNode(root, key):
    if not root: return None
    if key < root.val:
        root.left = deleteNode(root.left, key)
    elif key > root.val:
        root.right = deleteNode(root.right, key)
    else:
        if not root.left: return root.right
        if not root.right: return root.left
        min_node = root.right
        while min_node.left:
            min_node = min_node.left
        root.val = min_node.val
        root.right = deleteNode(root.right, min_node.val)
    return root

---

四、字典树（Trie）

1. 前缀匹配

🧩 208. 实现 Trie (前缀树)

python
class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False

class Trie:
    def __init__(self):
        self.root = TrieNode()
    
    def insert(self, word):
        node = self.root
        for c in word:
            if c not in node.children:
                node.children[c] = TrieNode()
            node = node.children[c]
        node.is_end = True
    
    def search(self, word):
        node = self.root
        for c in word:
            if c not in node.children:
                return False
            node = node.children[c]
        return node.is_end
    
    def startsWith(self, prefix):
        node = self.root
        for c in prefix:
            if c not in node.children:
                return False
            node = node.children[c]
        return True

2. 单词搜索 II

🧠 212. 单词搜索 II

python
def findWords(board, words):
    trie = Trie()
    for word in words:
        trie.insert(word)
    res = set()
    m, n = len(board), len(board[0])
    for i in range(m):
        for j in range(n):
            dfs(board, i, j, trie.root, "", res)
    return list(res)

def dfs(board, i, j, node, path, res):
    if node.is_end:
        res.add(path)
    if i < 0 or i >= len(board) or j < 0 or j >= len(board[0]) or board[i][j] not in node.children:
        return
    tmp = board[i][j]
    board[i][j] = "#"  # 标记已访问
    for dx, dy in [(-1,0),(1,0),(0,-1),(0,1)]:
        dfs(board, i+dx, j+dy, node.children[tmp], path+tmp, res)
    board[i][j] = tmp  # 回溯

---

五、高频树结构题目列表

类型	经典题目
树的遍历	144. 前序、102. 层序
递归问题	104. 最大深度、112. 路径总和
BST操作	98. 验证BST、450. 删除节点
字典树（Trie）	208. 实现Trie、212. 单词搜索 II

---

六、总结

树结构类题目的核心在于递归思想与结构特性的结合应用。

常用技巧包括：

1. ✅ 递归分治：如求深度、路径和
2. 💡 DFS/BFS遍历：前序、中序、后序、层序
3. 🔍 BST特性：左子树 < 根节点 < 右子树，中序遍历有序
4. 🧠 Trie树：高效字符串前缀匹配与查找

---

📌 学习建议路径：
树的遍历 → 递归问题 → BST性质 → Trie结构