二叉树的直径

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 来做一点优化。希望能帮助到有需要的小伙伴。

如果觉得不错的话，记得『三连』哦。小猪爱你们哟~

相关链接

• 活动题目列表
• leetcode 题解 repo
• 我的 segmentfault 专栏
• 我的知乎专栏