🌳 树形DP — 打家劫舍III与树的最大路径和

📖 树形DP的核心思想

树形DP是在树结构上做动态规划。树的后序遍历（先处理子节点再处理当前节点）天然对应DP的"从子问题到原问题"的填表顺序。树形DP的核心是：每个节点返回一个状态，父节点基于子节点的状态做决策。

1. 树形DP通用框架

def tree_dp(root):
    def dfs(node):
        if not node:
            return base_case
        left = dfs(node.left)   # 先处理左子树
        right = dfs(node.right) # 再处理右子树
        # 基于子树结果计算当前节点
        result = compute(node, left, right)
        return result
    return dfs(root)

🔬 题目一：打家劫舍III（LC 337）

在二叉树上打家劫舍，不能同时偷父子节点，返回能偷到的最大金额。

思路分析

代码实现

class Solution:
    def rob(self, root: Optional[TreeNode]) -> int:
        def dfs(node):
            if not node:
                return [0, 0]  # [rob, not_rob]
            left = dfs(node.left)
            right = dfs(node.right)
            # 偷当前节点：子节点不能偷
            rob = node.val + left[1] + right[1]
            # 不偷当前节点：子节点可偷可不偷
            not_rob = max(left) + max(right)
            return [rob, not_rob]
        return max(dfs(root))

复杂度分析

时间: O(n) 空间: O(h)

🔬 题目二：二叉树中的最大路径和（LC 124）

路径被定义为任意节点序列，每个节点最多出现一次。求路径上节点值之和的最大值。

思路分析

代码实现

class Solution:
    def maxPathSum(self, root: Optional[TreeNode]) -> int:
        max_sum = float('-inf')

        def dfs(node):
            nonlocal max_sum
            if not node:
                return 0
            # 负数贡献不要，取max(x, 0)
            left = max(dfs(node.left), 0)
            right = max(dfs(node.right), 0)
            # 经过当前节点的完整路径
            max_sum = max(max_sum, node.val + left + right)
            # 返回向下延伸的最大和（只能选一侧）
            return node.val + max(left, right)

        dfs(root)
        return max_sum

复杂度分析

时间: O(n) 空间: O(h)

🔬 题目三：二叉树的直径（LC 543）

二叉树的直径是任意两个节点间路径长度的最大值（边数）。

思路分析

代码实现

class Solution:
    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        diameter = 0

        def dfs(node):
            nonlocal diameter
            if not node:
                return 0
            left = dfs(node.left)
            right = dfs(node.right)
            diameter = max(diameter, left + right)
            return 1 + max(left, right)

        dfs(root)
        return diameter

复杂度分析

时间: O(n) 空间: O(h)

面试实战技巧

在实际面试中，算法题不仅仅是写代码，更考察沟通、分析和解决问题的能力。以下是一些实战技巧：

1. 解题步骤模板

2. 常见陷阱

3. 代码模板

# 通用解题模板
class Solution:
    def solve(self, input_data):
        # 1. 边界检查
        if not input_data:
            return default_value
        # 2. 初始化
        result = initial_value
        state = initial_state
        # 3. 主循环
        for item in input_data:
            state = transition(state, item)
            result = max/min/update(result, state)
        # 4. 返回结果
        return result

📝 课后练习

1. LC 1245 树的直径（无根树版本）
2. LC 968 监控二叉树（三种状态）
3. LC 834 树中距离之和（换根DP）
4. LC 337 打家劫舍III变形

🔑 本课要点回顾

• 树形DP核心：后序遍历=DP填表顺序
• 选/不选模型：每个节点返回[选的值,不选的值]
• 路径模型：dfs返回向下延伸的最大值
• 负数贡献不要：max(dfs(child), 0)
• 树形DP时间O(n)，空间O(h)

📚 扩展阅读

• 算法导论 树形DP章节
• 算法竞赛入门经典 树形DP
• 换根DP专题

⚡ 进阶专题：常见变体与扩展

每道经典题目都有丰富的变体。掌握核心模板后，灵活应对变体才是面试的真正挑战。以下列举本课相关的高频变体和扩展思路。

1. 常见题目变体

2. 面试中的沟通技巧

# 面试沟通模板
# 1. 先说思路（1-2分钟）
"这道题我想到两种解法，先说更直观的一种..."

# 2. 分析复杂度（30秒）
"时间复杂度O(n^2)，空间可以优化到O(n)"

# 3. 边写边说
"这里我定义dp[i]表示...，转移方程是..."

# 4. 主动验证
"我用示例走一遍：dp[0]=..., dp[1]=..."

# 5. 讨论优化
"空间还可以进一步优化，因为dp[i]只依赖..."

3. 代码调试检查清单

⚡ 树形DP进阶：换根DP

换根DP（Rerooting DP）是树形DP的高级技巧，适用于"以每个节点为根时求某个值"的问题。暴力做法O(n^2)，换根DP可以做到O(n)。

# LC 834 树中距离之和
def sumOfDistancesInTree(n, edges):
    graph = [[] for _ in range(n)]
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)

    size = [1] * n  # 子树大小
    dist = [0] * n  # 距离和

    # 第一遍DFS：以0为根
    def dfs1(u, parent):
        for v in graph[u]:
            if v != parent:
                dfs1(v, u)
                size[u] += size[v]
                dist[u] += dist[v] + size[v]

    # 第二遍DFS：换根
    def dfs2(u, parent):
        for v in graph[u]:
            if v != parent:
                dist[v] = dist[u] - size[v] + (n - size[v])
                dfs2(v, u)

    dfs1(0, -1)
    dfs2(0, -1)
    return dist