Hi 大家好，我是张小猪。欢迎来到『宝宝也能看懂』系列特别篇 - 官方小活动 『30-Day LeetCoding Challenge』。
这里是 4 月 11 号的题，也是题目列表中的第 543 题 -- 『二叉树的直径』
给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。
示例 :
给定二叉树
1
/ \
2 3
/ \
4 5返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。
注意： 两结点之间的路径长度是以它们之间边的数目表示。
EASY
题目的需求是求一颗二叉树的直径。第一眼看起来似乎有些不知道如何下手，不过我们尝试把这个问题拆解开来。站在一个节点的视角上看来这个目标，那其实只有两种情况：
- 这个最长路径以"我"为转折点：那么这个最长路径必然就是以"我"为根节点的子树左侧的高度 + 右侧的高度 + 1。
- 这个最长路径不以"我"为转折点：那么它一定以其他某个节点为转折点，对于"我"无需进行后续计算。
通过这种方式，我们成功的把目标拆解为了比较简单的小目标。然后我们只需要找到方法求出子树的高度即可。
通过深度优先遍历，我们可以轻松的求得某个子树的高度。为了避免大量的重复计算，我们可以用一个 map 把运算的结果进行暂存。最后再结合上面的思路，我们可以得到类似下面的代码：
const diameterOfBinaryTree = root => {
const cache = new Map();
let max = 0;
dfs(root);
return max;
function dfs(node) {
if (!node) return 0;
if (cache.has(node)) return cache.get(node);
const r = dfs(node.right);
const l = dfs(node.left);
if (max < r + l) max = r + l;
cache.set(node, Math.max(r, l) + 1);
return Math.max(r, l) + 1;
}
};分析的过程其实就是尝试把一个大目标拆分成很多的小目标来处理。而对于二叉树，我们常用的经典的遍历方式例如深度优先遍历，再结合 memo 来做一点优化。希望能帮助到有需要的小伙伴。
如果觉得不错的话，记得『三连』哦。小猪爱你们哟~
