LeetCode 二叉树直径

二叉树直径

思考

可以观察到两个现象

• 直径可能并不会经过根节点
• 所谓的直径就是某个节点的左子树深度加右子树深度最长的一条

那既然是获取最长的子树，是不能能套用一个之前的求 二叉树最大深度 的方法, 思考以下可以使用下面这个框架么

这可能行不通，因为提出了 maxDeep 方法导致调用时，只能作用在根节点的左右子树。替他节点无法调用这个模式递归。

const maxDeep = (root) => {
  if (root === null) return 0;
  return Math.max(maxDeep(root.left), maxDeep(root.right)) + 1;
};
var diameterOfBinaryTree = function (root) {
  //...
};

既然这样就放到内部去做, 但是这种框架面临的问题是，返回值只有一个，希望可以知道左右子树的最大深度，又要保留着已经遍历过的子树的最大直径。

var diameterOfBinaryTree = function (root) {
  if (root === null) return 0;

  let l = diameterOfBinaryTree(root.left);
  let r = diameterOfBinaryTree(root.right);

  // return Math.max(l + r, l, r) + 1;
};

那就再引入一个额外的变量去保存，最大直径，让递归可以专注与子树的最大深度

var diameterOfBinaryTree = function (root) {
  if (root === null) return 0;

  let max = 0;

  const dig = (root) => {
    if (root === null) return 0;
    let left = dig(root.left);
    let right = dig(root.right);
    max = Math.max(max, left + right);
    return Math.max(left, right) + 1;
  };

  dig(root);

  return max;
};

再来看一下，其实用前序遍历也可以实现，但是需要每经历一个节点，就要获取以下当前节点的左右子树的最大深度。

这是因为前序遍历只能获取当前节点的信息，而后序遍历则可以携带上一个节点返回的信息。

打赏