# [543. Diameter of Binary Tree] C++_Recursive_with brief explanation

• We can solve this problem with two different cases:

1. If the longest path will include the root node, then the longest path must be the depth(root->right) + depth (root->left)
2. If the longest path does not include the root node, this problem is divided into 2 sub-problem: set left child and right child as the new root separately, and repeat step1.

We could get the solution by returning the max path of 1 and 2.

``````class Solution {
public:
int diameterOfBinaryTree(TreeNode* root) {
if(root == nullptr) return 0;
int res = depth(root->left) + depth(root->right);
return max(res, max(diameterOfBinaryTree(root->left), diameterOfBinaryTree(root->right)));
}

int depth(TreeNode* root){
if(root == nullptr) return 0;
return 1 + max(depth(root->left), depth(root->right));
}
};``````

• This post is deleted!

• What is the time complexity? Thanks!

• this is the truth. i missed the rule 2 which is the core key of the question.

• 太棒啦！
Bravo!
Perfect!
すごい！

• I am afraid this is not a good solution as there are duplicate visits of the tree nodes.

• I am afraid this is not a good solution as there are duplicate visits of the tree nodes.

I agree, this visits nodes twice. That isn't really needed here, though it does make the solution look neater I guess..

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.