力扣HOT100之二叉树：543. 二叉树的直径

这道题本来想到可以用递归做，但是还是没想明白，最后还是去看灵神题解了，感觉这道题最大的收获就是巩固了我对lambda表达式的掌握。
按照灵神的思路，直径可以理解为从一个叶子出发向上，在某个节点处拐弯，然后向下到达另一个叶子，从而我们可以得到由两条链拼接起来的直径（也可能只有一条链）。既然直径一定会在某个节点拐弯，那我们可以枚举每个点，假设在这个节点拐弯，然后分别计算该节点的左右子树最长链（最大深度）然后+2，就得到了以当前节点为根节点的直径，我们使用一个全局变量来维护二叉树的最大直径，每当计算一个节点为根节点的最大直径时，就进行比较和更新。这里我们递归的作用并不是计算每个节点的直径，而是计算每个节点的左右子树中的最大链长，计算完之后二者相加，再顺带计算出当前节点的直径。

/**
 * 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 diameterOfBinaryTree(TreeNode* root) {
        int result = 0;
        //定义一个可以递归调用的lambda表达式
        //[可以访问的外部变量] (参数列表) -> 函数返回值类型 {函数体}
        auto dfs = [&] (this auto&& dfs, TreeNode* root) -> int {
            if(!root) return -1;   //遇到空节点则返回-1
            //注意，这里的链长不是直径，链长是不会拐弯的
            int left_len = dfs(root -> left) + 1;  //左子树最大链长 + 1
            int right_len = dfs(root -> right) + 1;   //右子树最大链长 + 1
            result = max(result, left_len + right_len);   //在当前节点处拐弯能否取得更大值
            return max(left_len, right_len);
        };
        //这里不要用result接收，因为dfs不是用来计算二叉树直径的
        //而是用来计算左右子树中的最大链长的
        dfs(root);  
        return result;
    }
};