Day 11 of 30-Day LeetCode Challenge

Given a binary tree, you need to compute the length of the diameter of the tree. The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root

/**
* 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 {
public:
int getHeight(TreeNode* root){
if(root==NULL) return 0;

return 1+max(getHeight(root->left), getHeight(root->right));
}

int getHeight2(TreeNode *root, int &max_diameter){
if(root==NULL) return 0;

int lh = getHeight2(root->left, max_diameter);
int rh = getHeight2(root->right, max_diameter);

max_diameter = max(max_diameter, 1+lh+rh);
return 1+max(lh, rh);
}


int diameterOfBinaryTree(TreeNode* root) {

// //O(n²) approach
// if(root==NULL) return 0;

// int leftDiameter = diameterOfBinaryTree(root->left);
// int myDiameter = getHeight(root->left) + getHeight(root->right);
// int rightDiameter = diameterOfBinaryTree(root->right);

// return max(leftDiameter, max(myDiameter, rightDiameter));

//O(n) approach
int max_diameter = 1;
getHeight2(root, max_diameter);
return max_diameter-1;
}
};