大家好，我就是那个在B站讲算法的「华南溜达虎」。
今天看到一位脉友吐槽当初面试极越汽车，面试官的态度特别傲慢让人非常反感，最后也没面上，现在想想有时候失去不一定是错的。这两天极越汽车原地解散，员工自费上班在网上闹得沸沸扬扬。从11月起全员停止缴纳社保，12月起开始自费上班，就算被裁签了补偿协议，也要等到2月15号兑现，大概率是无法兑现。
有脉友说太突然了，前几天极越还在内推招人。也有脉友说自己家附近12月初才开了一家极越汽车的新门店。也有内部人士表示极越的闪崩是早就注定的，只是外人不知道而已。
最近虎哥利用业余时间在B站讲算法，id「华南溜达虎」，我已经把算法面试高频题目列表blind75中的题目讲了一遍，力扣hot100也快讲完了，一个视频五分钟左右，利用空闲时间就把算法学会了，对跳槽找工作升职加薪甚至对考研都有帮助，感兴趣的同学可以 点击底部的「查看全文」 去学习一下。很多看过虎哥视频的同学都反馈讲的由浅及深，清晰明了，下面是一小部分评论截图。
言归正传，今天我们来分享一道高频面试题「螺旋矩阵」。
题目描述
给你一棵二叉树的根节点，返回该树的 直径 。
二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。
两节点之间路径的 长度 由它们之间边数表示。
举个例子：
输入：root = [1,2,3,4,5]
输出：3
解释：3 ，取路径 [4,2,1,3] 或 [5,2,1,3] 的长度。
思路解析
首先我们需要明确一个概念，两个节点之间路径的根节点，对于下图中4->2->1->3这条路径的根节点为1。
同样的对于下图中4->2->5这条路径的根节点为2。
接下来我们只需要枚举以二叉树中每一个节点为根节点的最长路径，在这些最长路径中选取一个最长的返回。
我们再明确一个概念，仅适用于本题，以node为根节点树的高度为节点node到叶子节点的最大边的个数。以上图中的节点2为例，以节点2为根节点的树的高度为1，因为从节点2到任意的叶子节点最多只有一条边。我们定义空节点的高度为-1，单个节点的高度为0。
以上图中的4->2->5这条路径为例，我们计算以节点2为根节点的最长路径path，需要知道节点2左子树的高度lhight = 0和右子树的高度rhight = 0，那么path = lhight + rhight + 2 = 2。同时我们还要更新以节点2为根节点的树的高度h = max(lhight, rhight) + 1 = 1，返回给节点2的父节点1使用。
上面整个过程只需要对二叉树的后序遍历稍加改造就可以实现。下面我们给出c++和python的两种代码实现。
c++代码
class Solution {
public:
int diameterOfBinaryTree(TreeNode* root) {
//二叉树最大路径的长度
int res = 0;
//以root为根节点的树的高度
int height = -1;
dfs(root, res, height);
return res;
}
void dfs(TreeNode* root, int& res, int& height) {
if (!root) {
height = -1;
return;
}
int lefthight = 0;
dfs(root->left, res, lefthight);
int righthight = 0;
dfs(root->right, res, righthight);
//更新全局最大路径的长度
res = max(res, lefthight + righthight + 2);
//更新以root为根节点的树的高度
height = max(lefthight, righthight) + 1;
}
};
python代码
class Solution:
def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
# 二叉树最大路径的长度
res = [0]
def dfs(root):
if not root:
return -1
lefthight = dfs(root.left)
righthight = dfs(root.right)
# 更新全局最大路径的长度
res[0] = max(res[0], lefthight + righthight + 2)
# 返回以root为根节点的树的高度
return max(lefthight, righthight) + 1
dfs(root)
return res[0]
复杂度分析
时间复杂度： 整个过程需要枚举二叉树中所有的节点，所以时间复杂度为O(n)，其中n为二叉树中节点的总数。
空间复杂度： 实现的过程使用了递归，递归需要用到函数栈，所以空间复杂度为O(h)，其中h为二叉树的高度。
号外
经常使用leetcode会员的同学可以使用我的优惠通道啦！
https://leetcode.cn/premium/?promoChannel=ldtiger ，年度会员有效期比官网多俩月，季度会员有效期比官网多两个星期，还有专属福利，需要的读者朋友可以找我了解。
今天的分享就到这里，希望大家能有所收获！
