树形动态规划——算法系列教程(c++版)

梦想不会自己发光，真正闪耀的是那个为梦狂奔的你。献给知行的孩子们！（Eric.He著）

动态规划的本质：它是一种 “以空间换时间”的优化算法，核心是把复杂问题拆解为多个重叠的子问题，通过记录子问题的最优解（状态），避免重复计算，最终由子问题的最优解推导出原问题的最优解。

算法回顾

动态规划的适用有三个核心前提（缺一不可），这也是判断一个问题是否能用 DP 解决的关键：
- 最优子结构：原问题的最优解包含其子问题的最优解；
- 重叠子问题：求解原问题时，会反复遇到相同的子问题（这是 DP 能优化的基础，否则不如暴力递归）；
- 无后效性：某一阶段的状态确定后，后续的状态推导只依赖当前状态，与状态的形成过程无关。

树形动态规划

树形动态规划是解决树结构上的最优解问题，比如 “树的最大路径和”“打家劫舍 III（树形）”。这类问题的特点是问题定义在树上，子问题对应树的子树，状态转移依赖于节点的子节点状态，解题时通常采用后序遍历（先求解子树，再求解当前节点）。

核心解题思路
- 定义状态：针对树的节点，定义两种状态（如 “选当前节点”/“不选当前节点”，dp[u][0]/dp[u][1]）；
- 后序遍历：递归遍历当前节点的所有子节点，先求解子节点的状态；
- 状态转移：根据子节点的状态，推导当前节点的状态（如dp[u][0] = sum(max(dp[v][0], dp[v][1]))，不选当前节点则子节点可选可不选）；
- 结果：根节点的最优状态（如max(dp[root][0], dp[root][1])）。

典型例题
- 二叉树的直径（LeetCode 543）：找二叉树中最长的路径（两个节点之间的边数最多）。
- 二叉树的最大路径和（LeetCode 124）：找二叉树中任意路径的最大和（路径可从任意节点开始，到任意节点结束）；
- 打家劫舍 III（LeetCode 337）：树形结构的打家劫舍，不能偷相邻节点，求最大偷取金额；

教程目录导航

▼

树形动态规划

一、二叉树的直径（LeetCode 543）

问题描述：

给你一棵二叉树的根节点，返回该树的直径。
- 二叉树的直径是指树中任意两个节点之间最长路径的长度。这条路径可能经过也可能不经过根节点 root 。
- 两节点之间路径的长度由它们之间边数表示。
提示：
- 树中节点数目在范围 [1, 10⁴] 内
- -100 <= Node.val <= 100
示例 1：
- 输入：root = [3,1,4,2,5]
- 输出：4
- 解释：4 ，取路径 [2,1,3,4,5] 的长度。
示例 2：
- 输入：root = [1,2]
- 输出：1

算法解析：

定义状态：dp[root] 表示以root为根的子树中，从root向下延伸的最长路径长度（边数）。
边界条件：dp[null] = 0（空节点没有向下路径，长度为 0）
状态转移：dp[root] = max(dp[root.left], dp[root.right]) + 1（+1 是 root 到子节点的边）
遍历顺序：按树的递归顺序（后序遍历，先子后父）
max_diameter 全局最优解


#include <iostream>
#include <vector>
#include <unordered_map>
#include"LinkedBSTree.h"
using namespace std;

int max_diameter; // 全局最优解（直径）
unordered_map<BSTNode<int>*, int> dp; // 显式存储dp[root]：key=节点，value=向下最长路径长度

// 计算dp[root]，并更新全局直径
int calculateDP(BSTNode<int>* root) {
    // 边界条件：空节点，dp值为0
    if (root == nullptr) {
        dp[root] = 0;
        return 0;
    }

    // 记忆化：如果已经计算过当前节点的dp值，直接返回（避免重复计算）
    if (dp.find(root) != dp.end()) {
        return dp[root];
    }

    // 状态转移：计算左右子节点的dp值（子问题）
    int left_dp = calculateDP(root->left);  // dp[left]
    int right_dp = calculateDP(root->right); // dp[right]

    // 更新全局最优解：当前节点作为拐点的路径长度 = dp[left] + dp[right]
    max_diameter = max(max_diameter, left_dp + right_dp);

    // 计算当前节点的dp值，并存储（记忆化）
    dp[root] = max(left_dp, right_dp) + 1;

    return dp[root];
}

int main() {
    LinkedBSTree<int> tree;

        tree.insertNode(3);
        tree.insertNode(1);
        tree.insertNode(4);
        tree.insertNode(2);
        tree.insertNode(5);
    
        //tree.levelOrder();
        BSTNode<int>* root = tree.getRoot();
        calculateDP(root);
        cout << max_diameter ;

    return 0;
}

输出结果

二、二叉树的最大路径和（LeetCode 124）

问题描述：

二叉树中的路径被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中至多出现一次。该路径至少包含一个节点，且不一定经过根节点。
- 路径和是路径中各节点值的总和。
- 给你一个二叉树的根节点 root ，返回其最大路径和。
提示：
- 树中节点数目范围是 [1, 3 * 10⁴]
- -1000 <= Node.val <= 1000
示例 1：
- 输入：root = [2,1,3]
- 输出：6
- 解释：最优路径是 1 -> 2 -> 3 ，路径和为 1 + 2 + 3 = 6
示例 2：
- 输入：root = [4,3,6,-5,5,7]
- 输出：20
- 解释：最优路径是 3 -> 4 -> 6 -> 7，路径和为 3 + 4 + 6 + 7 = 20

算法解析：

定义状态：dp[root] 表示以 root 为起点，向下延伸的最大路径和（路径只能向子节点延伸，不能分叉）。
状态转移：dp[root] = root.val + max(dp[root.left], dp[root.right], 0)：
- 加 root.val 是因为路径必须包含当前节点；
- max(..., 0) 是因为如果子树的路径和为负，不如不选（选了反而拉低当前路径和）；
全局最优解更新：按树的递归顺序（后序遍历，先子后父）
- 对每个节点 root，以其为拐点的路径和 = root.val + dp[root.left] + dp[root.right]；
- 遍历所有节点，取该值的最大值即为全局最大路径和。


#include <iostream>
#include <vector>
#include <algorithm>
#include <climits> // 用于INT_MIN
#include"LinkedBSTree.h"

using namespace std;

int max_sum; // 全局最大路径和

// 递归函数：返回以root为起点向下延伸的最大路径和（局部状态dp[root]）
int maxPathSum(BSTNode<int>* root) {
    if (root == nullptr) {
        return 0; // 空节点的局部路径和为0（无贡献）
    }

    // 计算左右子树的局部路径和（如果为负则取0，即不选该子树）
    int left_dp = max(maxPathSum(root->left), 0);
    int right_dp = max(maxPathSum(root->right), 0);

    // 更新全局最大路径和：当前节点作为拐点的路径和 = 根值 + 左局部 + 右局部
    max_sum = max(max_sum, root->data + left_dp + right_dp);

    // 返回当前节点的局部路径和：根值 + 左右局部的最大值（只能选一个方向延伸）
    return root->data + max(left_dp, right_dp);
}

int main() {
    max_sum = INT_MIN; // 初始化为最小整数（应对全负数的情况）
    LinkedBSTree<int> tree;

    tree.insertNode(2);
    tree.insertNode(1);
    tree.insertNode(3);

    //tree.levelOrder();
    BSTNode<int>* root = tree.getRoot();
    maxPathSum(root);
    cout << max_sum ;

    return 0;
}

输出结果

三、打家劫舍 III（LeetCode 337）

问题描述：

小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为 root 。
- 除了 root 之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。
- 给定二叉树的 root 。返回在不触动警报的情况下，小偷能够盗取的最高金额。
提示：
- 树的节点数在 [1, 10⁴] 范围内
- 0 <= Node.val <= 10⁴
示例 1：
- 输入：root = [5,3,6,4,7]
- 输出：16
- 解释：小偷一晚能够盗取的最高金额 5 + 4 + 7 = 16
示例 2：
- 输入：root = [4,3,6,2,5,7]
- 输出：18
- 解释：小偷一晚能够盗取的最高金额 2 + 4 + 5 + 7 = 18

算法解析：

定义状态：对每个节点 root，定义一个长度为 2 的数组 dp[root]：
- dp[root][0]：不选当前节点 root 时，以 root 为根的子树能盗取的最大金额；
- dp[root][1]：选当前节点 root 时，以 root 为根的子树能盗取的最大金额。
状态转移：
- 选当前节点 root（dp[root][1]）：则左右子节点都不能选，即 dp[root][1] = root.val + dp[left][0] + dp[right][0]；
- 不选当前节点 root（dp[root][0]）：则左右子节点可选可不选，取最大值，即 dp[root][0] = max(dp[left][0], dp[left][1]) + max(dp[right][0], dp[right][1])；
边界条件：空节点的两种状态都是 0（dp[null][0] = dp[null][1] = 0）。


#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 递归函数：返回当前节点的dp数组（{不选当前节点的最大值，选当前节点的最大值}）
pair<int, int> rob(BSTNode<int>* root) {
    // 边界条件：空节点，两种状态都是0
    if (root == nullptr) {
        return {0, 0};
    }

    // 递归计算左右子节点的dp状态（后序遍历，先子后父）
    auto [left_not, left_choose] = rob(root->left);
    auto [right_not, right_choose] = rob(root->right);

    // 状态转移1：选当前节点 → 左右子节点都不能选
    int choose = root->data + left_not + right_not;

    // 状态转移2：不选当前节点 → 左右子节点可选可不选，取最大值相加
    int not_choose = max(left_not, left_choose) + max(right_not, right_choose);

    // 返回当前节点的两种状态
    return {not_choose, choose};
}

int main() {
    LinkedBSTree<int> tree;

    tree.insertNode(5);
    tree.insertNode(3);
    tree.insertNode(6);
    tree.insertNode(4);
    tree.insertNode(7);

    //tree.levelOrder();
    BSTNode<int>* root = tree.getRoot();
    auto [not_choose_root, choose_root] = rob(root);
    cout << max(not_choose_root, choose_root) ;

    return 0;
}

输出结果

返回顶部