Given the root of a binary tree, return 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.
The length of a path between two nodes is represented by the number of edges between them.
Example 1:
Input: root = [1,2,3,4,5] Output: 3 Explanation: 3 is the length of the path [4,2,1,3] or [5,2,1,3].
Example 2:
Input: root = [1,2] Output: 1
Constraints:
- The number of nodes in the tree is in the range
[1, 104]. -100 <= Node.val <= 100
SOL：
參考李根逸博士影片的前半段，分為會經過root以及不會經過root兩種狀況。
經過root要用maxDepth算左右子樹的總和；沒經過的話就不會是最大深度，所以用diameterOfBinaryTree即可。
【C 語言的 LeetCode 30 天挑戰】第十一天 (Diameter of Binary Tree)
maxDepth參考：[LeetCode-C] 104. Maximum Depth of Binary Tree
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
int maxDepth(struct TreeNode* root){
if(root == NULL)
return 0;
int leftDepth = maxDepth(root->left);
int rightDepth = maxDepth(root->right);
return ((leftDepth>rightDepth)? leftDepth:rightDepth)+1;
}
int diameterOfBinaryTree(struct TreeNode* root){
if(root == NULL)
return 0;
// 1)經過root
int mid = maxDepth(root->left)+maxDepth(root->right);
// 2)沒經過root
int left = diameterOfBinaryTree(root->left);
int right = diameterOfBinaryTree(root->right);
int max = mid;
if(max<left)
max=left;
if(max<right)
max=right;
return max;
}
文章標籤
全站熱搜
烘焙 (2)