树的直径（树形DP）

题单来源，算法教程视频：树形 DP：树的直径【基础算法精讲 23】_哔哩哔哩_bilibili

1.二叉树的直径

题目：543. 二叉树的直径 - 力扣（LeetCode）

code

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:int ans = 0;int dfs(TreeNode* root){if(!root) return -1;int l = dfs(root->left) + 1, r = dfs(root->right) + 1;ans = max(ans, l + r);return max(l, r);}int diameterOfBinaryTree(TreeNode* root) {dfs(root);return ans;}
};

2.二叉树中的最大路径和

题目：124. 二叉树中的最大路径和 - 力扣（LeetCode）

上题为边权最大路径和，此题为最大点权路径和

code

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:int ans = -0x3f3f3f3f;int dfs(TreeNode* root){if(!root) return 0;int l = max(dfs(root->left), 0), r = max(dfs(root->right), 0);ans = max(ans, root->val + l + r);return max(l, r) + root->val;}int maxPathSum(TreeNode* root) {dfs(root);return ans;}
};

3.相邻字符不同的最长路径

题目：2246. 相邻字符不同的最长路径 - 力扣（LeetCode）

code

class Solution {
public:static const int N = int(1e5 + 20);int ans = 0;int n; string _s;vector<vector<int>> g;int dfs(int root){int max1 = 0, max2 = 0;for(int i : g[root]){int sz = dfs(i);if(_s[i] == _s[root]) continue;if(sz > max1) {max2 = max1;max1 = sz;}else if(sz > max2) max2 = sz;}ans = max(ans, max1 + max2 + 1);return max1 + 1;}int longestPath(vector<int>& parent, string s) {g.resize(N);n = parent.size();_s = s;for(int i = 0; i < n; i++){if(parent[i] < 0 ) continue;g[parent[i]].push_back(i);}dfs(0);return ans;}
};