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

 

解答：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
    int max=0;
public:
    int diameterOfBinaryTree(TreeNode* root) {
        if(root==NULL){
            return 0;
        }
        dfs(root);
        return max;
    }
private:
    int dfs(TreeNode* root){
    if(root->left==NULL&&root->right==NULL){
        return 0;
    }
    int leftSize=root->left==NULL?0:dfs(root->left)+1;
    int rightSize=root->right==NULL?0:dfs(root->right)+1;
    if(leftSize+rightSize>max)
        {
        max=leftSize+rightSize;
        }
    
    if(leftSize>=rightSize)return leftSize;
    else return rightSize;
    
}
};