Solution: We can use recursion to solve this problem. We need to be careful than this longest path can just reside in one of the sub-tree of the root. The code for this algorithm is as follow:
int height(TreeNode * root) { if(!root) return 0; return 1+max(height(root->left), height(root->right)); int Diameter(TreeNode *root) { if(!root) return 0; int h_left = height(root->left); int h_right = height(root->right); return max(1+h_left+h_right, max(Diameter(root->left), Diameter(root->right))); }
Memorization might be used to avoid repeated calculation.
No comments:
Post a Comment