开发笔记:力扣543：二叉树的直径C++

给定一棵二叉树&＃xff0c;你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。

这道题的难度在LeetCode上被归为简单&＃xff0c;但我觉得这道题无论是思路上还是代码的写法上&＃xff0c;还有具有中等难度的程度的。

这道题要求我们计算直径长度&＃xff0c;首先我们要将求直径长度转换成一个好求的量&＃xff0c;笔者将求直径长度转换为求二叉树的高度。这个其实是不难理解的&＃xff0c;因为直径其实就是经过边的个数&＃xff0c;每经过一条边&＃xff0c;相当于高度增加1。

但是题中说明了这条路径可能穿过根结点&＃xff0c;因此最长的路径显然是左子树的高度&＃43;右子树的高度。

分析到这里&＃xff0c;可能有的小伙伴会想&＃xff0c;那这个不难呀&＃xff0c;我用递归的方法求出左子树的高度和右子树的高度&＃xff0c;返回它们之和就是题解了。于是写出这样的代码&＃xff1a;

class Solution {
public:
int diameterOfBinaryTree(TreeNode* root) {
if(!root)return 0;
int left&＃61;GetHeight(root->left);//求左子树高度
int right&＃61;GetHeight(root->right);//求右子树高度
return left&＃43;right;
}
int GetHeight(TreeNode* root){//递归求解高度
if(!root)return 0;
return 1&＃43;max(GetHeight(root->left),GetHeight(root->right));
}
};


虽然思路是正确的&＃xff0c;但是这样由于少考虑了一种情况而导致部分用例会出现错误。

比如这个用例&＃xff0c;按照上述代码的话&＃xff0c;输出的答案是左子树高度1&＃43;右子树高度6&＃61;7。然而其最大路径实际上是以第三层-9这个父结点作为根结点时&＃xff0c;此时左子树高度4&＃43;右子树高度&＃61;8。这就要求我们要结合后序遍历&＃xff0c;实现从下往上求出每个父结点作为根结点时&＃xff0c;左右子树高度和&＃xff0c;并与下次求出的值作比较&＃xff0c;保留较大值。

按照这个思路&＃xff0c;就可以写代码了。

class Solution {
int maxlength&＃61;INT_MIN;//定义一个存储最大路径的变量
public:
int diameterOfBinaryTree(TreeNode* root) {
if(!root)return 0;
dfs(root);//后序dfs
return maxlength;
}
int GetHeight(TreeNode* root){//求root高度的函数
if(!root)return 0;
return 1&＃43;max(GetHeight(root->left),GetHeight(root->right));
}
void dfs(TreeNode* root){
if(!root)return;
dfs(root->left);
dfs(root->right);
maxlength&＃61;max(maxlength,GetHeight(root->left)&＃43;GetHeight(root->right));//将maxlength与当前父结点左右子树高度和比较&＃xff0c;保留较大值
}
};