LeetCode 第1热题第2课

1 543. 二叉树的直径

【这道题目与 124. 二叉树中的最大路径和 非常相似。

关键点在于，二叉树的 直径 指的是树中任意两个节点之间 最长路径的长度。

简单来说，就是寻找一条路径，使得这条路径所包含的节点数量达到最大。

解题方法如下：

• 采用自底向上的方式遍历整棵二叉树
• 当前子树中最长的路径长度等于 1 加上左子树中最长路径长度再加上右子树中最长路径长度
• 向父节点传递当前子树中最长路径长度时，取值为 1 加上左子树和右子树中最长路径长度的最大值

为何必须在 “左子树中的最长路径” 和 “右子树中的最长路径” 中选择一个？难道不能同时取用吗？显然不行。因为我们需要的是单一的一条直线型路径，若同时选取左右两部分，则会导致路径出现分叉现象。

思路说明图：

针对绿色节点而言，当其作为子树根节点时，该子树的最长路径长度可表示为1加上左子树最长路径与右子树最长路径之和；此时绿色节点（作为左子节点）会向其父节点（蓝色节点）提交自身所计算出的最长路径值，该值等于1加上左子树与右子树中最