/**
knakul853
 */
class Solution {
public:
    int diameterOfBinaryTree(TreeNode* root) {

        return dfs(root).first;

    }

    // max of {left+right, lft, right}  {di, hight};

  pair<int,int>  dfs(TreeNode* root)
    {
          if(!root)return{0,0};

          auto p1 = dfs(root->left);
          auto p2 = dfs(root->right);

         int dim = max({p1.first, p2.first, p1.second + p2.second});

      return {dim, max(p1.second, p2.second)+1};

    }
};

class Solution {
public:
    int mx = 0;
    int diameterOfBinaryTree(TreeNode* root) {
        if(!root)return 0;

      f(root);
        return mx;

    }

    int f(TreeNode* root)
    {
         if(!root)return 0;

        int l = f(root->left);
        int r = f(root->right);
        mx = max(mx , l+r);
        return max(l,r)+1;
    }

};