二叉树的直径

给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。

注意：两结点之间的路径长度是以它们之间边的数目表示。

543.二叉树的直径

小黎当时第一眼看到就想起来了之前刷过的二叉树最大路径和

用了类似的思路，写了以下代码：

/**
 * 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 {
    int ans = -INT_MAX;
public:
    int diameterOfBinaryTree(TreeNode* root) {
        int res = recur(root);
        return max(res, ans);
    }
    int recur(TreeNode* root){
        if(root == nullptr || (root->left == nullptr && root->right == nullptr)){
            return 0;
        }
        int left = recur(root->left);
        int right = recur(root->right);
        if(root->left && root->right){
            ans = max({ans, 1 + left, 1 + right, left + 2 + right});
            return max({1 + left, 1 + right, 0});
        }else if(root->left){
            ans = max(ans, 1 + left);
            return max(0, 1 + left);
        }else{
            ans = max(ans, 1 + right);
            return max(0, 1 + right);
        }
        
    }
};

过是过了，性能也不差，但是这个代码也太冗余了，还要判断左右子树是否为空。主要是因为如果子树为空，那就不能连接过去，就不能盲目地+1

后面感觉既然空树返回的是0，而且如果要和上端相连最多只能取一个子树。以及ans只用于从左子树通过根连接到右子树的情况，就改了一下：

/**
 * 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 {
    int ans = -INT_MAX;
public:
    int diameterOfBinaryTree(TreeNode* root) {
        int res = recur(root);
        return max(res, ans);
    }
    int recur(TreeNode* root){
        if(root == nullptr || (root->left == nullptr && root->right == nullptr)){
            return 0;
        }
        int left = recur(root->left);
        int right = recur(root->right);
        if(root->left && root->right){
            ans = max(ans, left + 2 + right);
        }
        return max(0, 1 + max(left, right));
    }
};

时间已经击败100%了，凑合过吧

后面看到官方题解是用经过的最大节点数-1做的。感觉和我的也差不了太多，勉强贴上来吧：

class Solution {
    int ans;
    int depth(TreeNode* rt){
        if (rt == NULL) {
            return 0; // 访问到空节点了，返回0
        }
        int L = depth(rt->left); // 左儿子为根的子树的深度
        int R = depth(rt->right); // 右儿子为根的子树的深度
        ans = max(ans, L + R + 1); // 计算d_node即L+R+1 并更新ans
        return max(L, R) + 1; // 返回该节点为根的子树的深度
    }
public:
    int diameterOfBinaryTree(TreeNode* root) {
        ans = 1;
        depth(root);
        return ans - 1;
    }
};

这样就省略了子树是否为空的计算，还是比我的做法要优雅亿些的~