Straightforward DFS solution:
class Solution {
public:
int diameterOfBinaryTree(TreeNode* root) {
if (root == NULL)
return 0;
int ans = 0;
calcDiameter(root, ans);
return ans-1;
}
int calcDiameter (TreeNode* node, int& ans) {
if (node == NULL)
return -1; // since we do 1 + calcDiameter(...), we have to return -1 as left=right=0 in case of leaf node
int left = 1 + calcDiameter(node->left, ans);
int right = 1 + calcDiameter(node->right, ans);
ans = max(ans, left+right+1);
return max(left, right);
}
};
Similar idea, simpler code:
int ans = 0;
int diameterOfBinaryTree(TreeNode* root) {
if (root == NULL)
return 0;
calcDiameter(root);
return ans-1;
}
int calcDiameter (TreeNode* node) {
if (node == NULL)
return 0;
int left = calcDiameter(node->left);
int right = calcDiameter(node->right);
ans = max(ans, left+right+1);
return max(left, right)+1;
}