Leetcode 543. 124. 二叉树的直径 树形dp C++实现
问题：Leetcode 543. 二叉树的直径（边权型）
给你一棵二叉树的根节点，返回该树的 直径 。
二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。两节点之间路径的 长度 由它们之间边数表示。
/*** 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) {}* };*/
算法：
求最长链相当于左右子树的最大深度相加。所以分别求出左右子树的最大深度，然后相加放入 ans 。
时间复杂度：O(n) 。其中 n 为二叉树的节点个数。
空间复杂度：O(n) 。最坏情况下，二叉树退化成一条链，递归需要 O(n) 的栈空间。
代码：
class Solution {
public:int diameterOfBinaryTree(TreeNode* root) {int ans = 0;auto dfs = [&](auto &&dfs,TreeNode *node){if(!node) return -1;int l_len = dfs(dfs,node->left) + 1;int r_len = dfs(dfs,node->right) + 1;ans = max(ans,l_len+r_len);return max(l_len,r_len);};dfs(dfs,root);return ans;}
};问题：Leetcode 124. 二叉树中的最大路径和（点权型）
二叉树中的 路径 被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。路径和 是路径中各节点值的总和。
给你一个二叉树的根节点 root ，返回其 最大路径和 。
/*** 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) {}* };*/
算法：
从 root 结点开始向下递归，枚举每个 node ，返回从 node 到该条路径叶子结点的最大值，如果有分支，则比较左右大小，返回最大值。
注意，如果最后结果是负的，则返回 0 ，因为可以放弃这段路径。
本题有两个关键概念：
链：从叶子到当前节点的路径。其节点值之和是 dfs 的返回值。
直径：等价于由两条（或者一条）链拼成的路径。我们枚举每个 node ，假设直径在这里拐弯，也就是计算由左右两条从叶子到 node 的链的节点值之和，去更新答案的最大值。
⚠注意：dfs 返回的是链的节点值之和，不是直径的节点值之和。
时间复杂度：O(n) ，其中 n 为二叉树的节点个数。
空间复杂度：O(n) 。最坏情况下，二叉树退化成一条链，递归需要 O(n) 的栈空间。
代码：
class Solution {
public:int maxPathSum(TreeNode* root) {int ans = INT_MIN;auto dfs = [&](auto &&dfs,TreeNode *node) -> int{if(!node) return 0;int l_val = dfs(dfs,node->left);int r_val = dfs(dfs,node->right);ans = max(ans,l_val + r_val + node->val);return max(max(l_val,r_val) + node->val,0);};dfs(dfs,root);return ans;}
};