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 levelreturn 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 消耗深度​​​​​​​​​