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;
    }
};