树形 DP：树的直径

leetCode 104.二叉树的最大深度104. 二叉树的最大深度 - 力扣（LeetCode）

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

leetCode 543.二叉树的直径 543. 二叉树的直径 - 力扣（LeetCode）

换个角度看直径：从一个叶子出发向上，在某个节点“拐弯”，向下到达另一个叶子，得到了由两条链拼起来的路径。（也可能只有一条链）

算法：遍历二叉树，在计算最长链的同时，顺带把直径算出来

• 在当前节点“拐弯”的直径长度 = 左子树的最长链 + 右子树的最长链 + 2
• 返回给父节点的是以当前节点为根的子树的最长链 = max(左子树的最长链,右子树的最长链)+1

class Solution {
public:int diameterOfBinaryTree(TreeNode* root) {int ans=0;function<int(TreeNode*)>dfs =[&](TreeNode* node) -> int {if(node == nullptr) return -1;// 下面+1后，对于叶子节点就刚好是 0int left = dfs(node->left);int right = dfs(node->right);ans = max(ans,left+right+2);return max(left,right)+1; //当前子树最大链长};dfs(root);return ans;}
};

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

算法：遍历二叉树，在计算最大链和的同时，顺带更新答案的最大值

• 在当前节点 "拐弯" 的最大路径和 = 左子树最大链和 + 右子树最大链和 + 当前节点值
• 返回给父节点的是max(左子树最大链和,右子树最大链和)+当前节点值。如果这个值是负数，则返回 0 

class Solution:def maxPathSum(self, root: Optional[TreeNode]) -> int:ans = -infdef dfs(node):if node is None:return 0l_val = dfs(node.left)r_val = dfs(node.right)nonlocal ansans = max(ans,l_val+r_val+node.val)return max(max(l_val,r_val) + node.val,0)dfs(root)return ans

2246.相邻字符不同的最长路径（1245.树的直径）2246. 相邻字符不同的最长路径 - 力扣（LeetCode）

class Solution {
public:int longestPath(vector<int>& parent, string s) {int n = parent.size();vector<vector<int>> g(n);for(int i=1;i<n;i++) {g[parent[i]].push_back(i);}int ans = 0;function<int(int)> dfs = [&](int x) -> int {int maxLen = 0;for (int y : g[x]) {int len = dfs(y) + 1;if (s[y] != s[x]) {ans = max(ans, maxLen + len);maxLen = max(maxLen, len);}}return maxLen;};dfs(0);return ans+1;}
};// -1 0 0 1 1 2
//  0 1 2 3 4 5//   0:[1,2]
//   1:[3,4]
//   2:[5]

推荐文章和参考视频：

树形 DP：树的直径【基础算法精讲 23】_哔哩哔哩_bilibili

543. 二叉树的直径 https://leetcode.cn/problems/diameter-of-binary-tree/solution/shi-pin-che-di-zhang-wo-zhi-jing-dpcong-taqma/
124. 二叉树中的最大路径和 https://leetcode.cn/problems/binary-tree-maximum-path-sum/solution/shi-pin-che-di-zhang-wo-zhi-jing-dpcong-n9s91/
2246. 相邻字符不同的最长路径 https://leetcode.cn/problems/longest-path-with-different-adjacent-characters/solution/by-endlesscheng-92fw/