题意：


方法一：
递归

思路：
        核心：当前节点的直径=左子树高度+右子树高度。
        递归整棵树，以每个节点作为根节点，计算当前节点的直径=左子树高度+右子树高度，并维护直径的最大值。
        因此，要写个递归函数求解每个子树的高度。（后序遍历）
        计算每个子树的高度=max(左子树的高度,右子树的高度)+1。

    

class Solution {
public:
    int res=0;
    int diameterOfBinaryTree(TreeNode* root) {
        dfs(root);//递归
        return res;
    }
    
    int dfs(TreeNode *root){//递归计算子树的高度
        if(root==nullptr)
            return 0;
        int l=dfs(root->left);
        int r=dfs(root->right);
        res=max(res,l+r);//直径=
        return max(l,r)+1;//子树的高度等于max(左子树的高度,右子树的高度)+1
    }
};


时间复杂度：
空间复杂度：

方法二：
java

思路：
        思路与方法一相同。 

import java.util.*;

public class Solution {
    int res=0;
    public int diameterOfBinaryTree (TreeNode root) {
        dfs(root);//递归
        return res;
    }
    
    int dfs(TreeNode root){//递归计算子树的高度
        if(root==null)
            return 0;
        int l=dfs(root.left);
        int r=dfs(root.right);
        res=Math.max(res,l+r);//当前节点的直径=左子树高度+右子树高度
        return Math.max(l,r)+1;//子树的高度=max(左子树的高度,右子树的高度)+1
    }
}

时间复杂度：
空间复杂度：