543. 二叉树的直径

题目

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

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

输入输出

input:[1,2,3,4,5]
output:3

input:[4,-7,-3,null,null,-9,-3,9,-7,-4,null,6,null,-6,-6,null,null,0,6,5,null,9,null,null,-1,-4,null,null,null,-2]
output:8

代码

/**
 * 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 res = 0,mmm = 0;
        if(root==nullptr){
            return 0;
        }
		//求分别以该节点，该节点的左子树与右子树为根的长度
        res = max(res,max(diameterOfBinaryTree2(root),max(diameterOfBinaryTree2(root->right),diameterOfBinaryTree2(root->left))));
		//递归每个节点，以每个节点为根求最大值
        res = max(res,max(diameterOfBinaryTree(root->right),diameterOfBinaryTree(root->left)));
        return res;
    }

    //求以该节点为根，左右两颗子树的长度之和，即最大长度
    int diameterOfBinaryTree2(TreeNode* root) {
        int res = 0;
        if(root==nullptr){
            return 0;
        }
        return res+diameterOfBinaryTree1(root->right)+diameterOfBinaryTree1(root->left);

    }
	
	//求左右子树边的数量
    int diameterOfBinaryTree1(TreeNode* root) {
        int res = 0;
        if(root==nullptr){
            return 0;
        }
        res++;
        res+=max(diameterOfBinaryTree1(root->right),diameterOfBinaryTree1(root->left));
        return res;

    }
};