LeetCode刷题实战543：二叉树的直径
共 2161字，需浏览 5分钟
·
2022-03-10 17:17
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.
示例
解题
class Solution {
public:
int md, td;
int diameterOfBinaryTree(TreeNode* root) {
if (!root)
return 0;
md = td = 0;
preOrder(root);
return md;
}
int maxDepth(TreeNode *root)//计算每个节点（根节点）的左右子树最大深度
{
if (!root)
return 0;
if (root->left == NULL && root->right == NULL)
return 1;
else if (!root->left)
return maxDepth(root->right)+1;
else if (!root->right)
return maxDepth(root->left)+1;
else
return max(maxDepth(root->left), maxDepth(root->right))+1;
}
void preOrder(TreeNode *root)//遍历每个节点，把遍历到的每个节点作为根节点
{
if (!root)
return;
td= maxDepth(root->left) + maxDepth(root->right);
md = max(md, td);
preOrder(root->left);
preOrder(root->right);
}
};
class Solution {
public:
int diameterOfBinaryTree(TreeNode* root) {
int res=0;
depth(root,res);
return res;
}
private:
int depth(TreeNode *root,int &res){
if (!root) return 0;
int left_depth=depth(root->left,res);
int right_depth=depth(root->right,res);
res=max(res,right_depth+left_depth);
return max(left_depth+1,right_depth+1);
}
};