Leetcode 每日一题：Diameter of Binary Tree
写在前面：
最近被学校的 campus involvement 社团活动的招新宣传和选拔，以及找工作频繁的参加招聘会和网上申请忙的焦头烂额，马上又要到来的期中考试让我再次意识到了大学生活的险恶。虽然大家都说学生时代是最幸福的时代，但这个幸福也是相对的吧～～
今天我们来一道简单一点的题目练练手，但是这道题目简单并不代表他没有进行深究的价值。理解这道题目的解法对于理解 Binary Tree 的结构，DFS 和 Recursion 的算法应用都有比较深的基础价值和意义，就让我们一起来看看吧！
题目介绍：
- 题目链接：https://leetcode.com/problems/diameter-of-binary-tree/description/
- 题目类型：Binary Tree，DFS，Recursion
- 题目难度：Easy
- 题目来源：Google 高频面试题
题目想法：
如何确定最大 diameter 来自于哪里：
这道题的难点在于如何确定 最大 diameter 是产出于哪里，因为如果这个产出是随机且没有规律的话，这道题将会变成一道非常困难的问题，所以我们首先要明确如何找出 最大的 diameter 产出于哪里？
最大的 diameter：一定是 leaf node 到另外一个 leaf node
为什么呢？ 我们可以做一个简短的举反例证明， proof by contradiction：
- 如果我们的最大 diameter 起终点产出于一个不是 leaf node 的节点
- 不是 leaf node 节点的 node 一定有至少一个 children 节点
- 那我们的最大 diameter 就还可以在不影响其任何已经组成节点的情况下新加入一个 leaf node，让其长度 + 1
- 那原本的这个 不是leaf node 的节点就不能是 最长 diameter
- 所以最长 diameter 一定是从一个leaf node 到另一个 leaf node
如何 Construct 最大 diameter
既然我们已经确定好了最大的 diameter 一定是从一个 leaf node 到另一个 Leaf node，那我们在每一个点的时候，最大的 diameter 一定是来自于：
maxCurrent = leftMax + rightMax
因为当前这个点，能组成的 diameter 最大就是从他最左侧的 leafnode，到最右侧的 leafnode，这其中最长的一个，又因为我们统计的是 edge 个数，所以就是 左侧最深 + 右侧最深即可
题目解法：
- DFS 遍历每一个数的节点：
- 如果当前节点是空，返回0
- 当前最大深度 = 左侧最大深度 + 右侧最大深度
- 更新最大深度
- 返回当前节点最大深度 = max（左侧最大， 右侧最大）
题目代码：
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int DFS(TreeNode* root, int& maxDepth){
if(root == nullptr){
return 0;
}
//update the maxDepth if needed:
int leftMax = DFS(root->left, maxDepth);
int rightMax = DFS(root->right, maxDepth);
maxDepth = max(maxDepth, leftMax + rightMax);
//update the current route's max to the upper level
return max(leftMax, rightMax) + 1;
}
int diameterOfBinaryTree(TreeNode* root) {
int maxDepth = 0;
int maxSubDepth = DFS(root, maxDepth);
return maxDepth;
}
};- Runtime: O(N) 遍历每一个点一次
- Space：O(N) 有多少个点决定了我们的 recursion 的 space 消耗深度