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.
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].
Note: The length of path between two nodes is represented by the number of edges between them.
解题思路
本题要求最长路径长,可以转化为求最长路径中的节点个数-1
最长路径包含以下三种情况:
1 根节点包含在最长路径中,则节点个数 = 左树高 + 右树高 + 1
2 最长路径在左子树中,则可以求左子树的最长路径的节点数目
3 最长路径在右子树中,则可以求右子树的最长路径的节点数目
对这三种情况进行比较,即可求出最长路径
代码
class Solution {
public:
int diameterOfBinaryTree(TreeNode* root) {
if (root == NULL) {
return 0;
}
return numOfNode(root) - 1;
}
int numOfNode(TreeNode* root) {
if (root == NULL) {
return 0;
}
//根节点包含在最长路径中
int ans = 1 + height(root->left) + height(root->right);
//最长路径在左子树中
ans = max(ans, numOfNode(root->left));
//最长路径在右子树中
ans = max(ans, numOfNode(root->right));
return ans;
}
int height(TreeNode* root) {
if (root == NULL) {
return 0;
}
int l = 1, r = 1;
if (root->left != NULL) {
l += height(root->left);
}
if (root->right != NULL) {
r += height(root->right);
}
return max(l, r);
}
};
我们可以看到,在每一次计算根节点包含在最长路径中的情况时,都要求一遍树高。而求树高是用递归实现的。在平衡二叉树的情况下,T(n) = 2 * T(n/2) + O(n),时间复杂度为O(nlogn)。在树退化为链的情况下,时间复杂度更是达到了O(n^2)
那么,有没有办法在线性时间内求解呢?
通过观察,我们发现,在求最长路径时,每一次数值的计算都用到了树高。换而言之,每求得一次左右子树树高我们就计算一次包含该根节点的最长路径,这样,遍历完整棵树时,我们也就得到了整棵树的最长路径。
class Solution {
public:
int ans = 1;
int diameterOfBinaryTree(TreeNode* root) {
if (root == NULL) {
return 0;
}
height(root);
return ans - 1;
}
int height(TreeNode* root) {
if (root == NULL) {
return 0;
}
int l = 1, r = 1;
if (root->left != NULL) {
l += height(root->left);
}
if (root->right != NULL) {
r += height(root->right);
}
//原式为左子树高+右子树高+1,此处算了两次根节点,故-1
ans = max(ans, l + r - 1);
return max(l, r);
}
};
网友评论