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.
- The length of path between two nodes is represented by the number of edges between them.
Example:
- Given a binary tree
1
/
2 3
/
4 5
- Return 3, which is the length of the path [4,2,1,3] or [5,2,1,3].
C Solution 1:
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
#define MAX(a, b) ((a) > (b) ? (a) : (b))
void postorder(struct TreeNode *root, int *left, int *right, int *res) {
if (!root) {
*left = -1;
*right = -1;
return;
}
int _left, _right;
postorder(root->left, &_left, &_right, res);
*left = MAX(_left, _right) + 1;
postorder(root->right, &_left, &_right, res);
*right = MAX(_left, _right) + 1;
if (*left + *right > *res) *res = *left + *right;
}
int diameterOfBinaryTree(struct TreeNode* root) {
int left, right, res = 0;
postorder(root, &left, &right, &res);
return res;
}
C Solution 2:
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
int maxdepth(struct TreeNode *root, int *res) {
if (!root) return -1;
int left = maxdepth(root->left, res);
int right = maxdepth(root->right, res);
*res = *res > (left + right + 2) ? *res : (left + right + 2);
return (left > right ? left : right) + 1;
}
int diameterOfBinaryTree(struct TreeNode* root) {
int res = 0;
maxdepth(root, &res);
return res;
}
C Solution 3:
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
int maxdepth(struct TreeNode *root, int *res) {
if (!root) return 0;
int left = maxdepth(root->left, res);
int right = maxdepth(root->right, res);
*res = *res > (left + right) ? *res : (left + right);
return (left > right ? left : right) + 1;
}
int diameterOfBinaryTree(struct TreeNode* root) {
int res = 0;
maxdepth(root, &res);
return res;
}
Python Solution:
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def diameterOfBinaryTree(self, root):
"""
:type root: TreeNode
:rtype: int
"""
def recu(root):
if not root: return 0, 0
left_dia, left_high = recu(root.left)
right_dia, right_high = recu(root.right)
cur_dia = left_high + right_high
dia = max(left_dia, right_dia, cur_dia)
high = (left_high if left_high > right_high else right_high) + 1
return dia, high
dia, high = recu(root)
return dia
Summary:
- from bottom to top
LeetCode: 543. Diameter of Binary Tree
近期评论