#include <iostream>

using namespace std;

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 calculatorDiameter(TreeNode* root, int& ans) {
        if(!root) return 0;
        //计算左子树最长
        int lNum = calculatorDiameter(root->left, ans);
        //计算右子树最长
        int rNum = calculatorDiameter(root->right, ans);
        //记录最优值
        ans = max(ans, lNum + rNum + 1);
        return max(lNum, rNum) + 1;
    }
    int diameterOfBinaryTree(TreeNode* root) {
        int ans = 0;
        calculatorDiameter(root, ans);
        return ans - 1;
    }
};

TreeNode* test() {
    TreeNode* root = new(TreeNode);
    root->val = 1;

    TreeNode* p1 = new(TreeNode);
    TreeNode* p2 = new(TreeNode);
    root->left = p1;
    root->right = p2;

    TreeNode* p3 = new(TreeNode);
    TreeNode* p4 = new(TreeNode);

    p1->left = p3;
    p1->right = p4;

    p2->left = nullptr;
    p2->right = nullptr;

    p3->left = nullptr;
    p3->right = nullptr;

    p4->left = nullptr;
    p4->right = nullptr;
    return root;
}

int main()
{
    TreeNode* root = test();
    Solution obj;
    cout<<obj.diameterOfBinaryTree(root)<<endl;
    return 0;
}