当前位置：首页 > news >正文

树形 DP

news 2026/3/27 1:19:20

二叉树的最大深度

解题思路

二叉树的最大深度 = max(左子树的最大深度，右子树的最大深度)+1

代码实现

点击查看代码

class Solution {
public:int maxDepth(TreeNode* root) {if (root == nullptr) {return 0;}return max(maxDepth(root->left), maxDepth(root->right)) + 1;}
};

二叉树的直径

解题思路

定义节点的高度：从该节点到最远叶子节点的边数。空节点的高度为-1，叶子节点的高度为0。
一个节点的高度 = max(左子树高度，右子树高度)+1

对每个节点，计算【经过该节点的最长路径】：左子树高度 + 右子树高度 + 2

代码实现

点击查看代码

class Solution {
public:int diameterOfBinaryTree(TreeNode* root) {int ans = 0;auto dfs = [&](this auto&& dfs, TreeNode* root) -> int {if (root == nullptr) {return -1;}int l_len = dfs(root->left);int r_len = dfs(root->right);ans = max(ans, l_len + r_len + 2);return max(l_len, r_len) + 1;};dfs(root);return ans;}
};

时间复杂度：\(O(n)\)
空间复杂度：\(O(n)\)

二叉树中的最大路径和

代码实现

点击查看代码

class Solution {
public:int maxPathSum(TreeNode* root) {int ans = -INT_MAX;auto dfs = [&](this auto&& dfs, TreeNode* root) -> int {if (root == nullptr) {return 0;}int l_val = dfs(root->left);int r_val = dfs(root->right);ans = max(ans, l_val + r_val + root->val);return max(max(l_val, r_val) + root->val, 0);};dfs(root);return ans;}
};

相邻字符不同的最长路径

解题思路

思路1

遍历 \(x\) 的子树，把最长链的长度都存到一个列表中，排序，取最大的两个。

思路2

遍历 \(x\) 的子树的同时维护最长链 \(a\) 和次长链 \(b\)。
如何一次遍历找最长+次长？

如果次长在前面，最长在后面，那么遍历到最长的时候就能算出最长+次长
如果最长在前面，次长在后面，那么遍历到次长的时候就能算出最长+次长

战略性放弃

打家劫舍 III

解题思路

选或不选

选当前节点，左右儿子都不能选
不选当前节点，左右儿子可选可不选

提炼状态
对于每个节点，都有选或不选两个状态

选 = 左不选的最大点 + 右不选的最大点 + 当前节点值
不选 = max(左选，左不选) + max(右选，右不选)

最终答案：对于根节点，选或不选

代码实现

点击查看代码

class Solution {
public:int rob(TreeNode* root) {auto dfs = [](this auto&& dfs, TreeNode* root) -> pair<int, int> {if (root == nullptr) {return {0, 0}; // 选 不选}auto l = dfs(root->left);auto r = dfs(root->right);int rob = l.second + r.second + root->val;int not_rob = max(l.first, l.second) + max(r.first, r.second);return {rob, not_rob};};auto res = dfs(root);return max(res.first, res.second);    }
};