自底向上的信息聚合

如何计算二叉树的最大深度？

• 定义: 根节点到最远叶节点的节点数 (LeetCode 口径);
• 递推: maxDepth(node) = max(maxDepth(left), maxDepth(right)) + 1, 空节点返回 0;

const maxDepth = function (root) {
  const dfs = (node) => (node == null ? 0 : Math.max(dfs(node.left), dfs(node.right)) + 1);
  return dfs(root);
};

最小深度与最大深度的差别在哪？

• 陷阱: 空子树不是有效路径, 不能直接对所有子树取 min;
• 规则: 只有一侧子树时, 最小深度由非空那一侧决定;
• 递推: 叶节点返回 1; 单侧为空时返回另一侧加 1; 两侧都存在时取较小值加 1;

const minDepth = function (root) {
  const dfs = (node) => {
    if (node == null) return 0;
    if (node.left == null && node.right == null) return 1;
    if (node.left == null) return dfs(node.right) + 1;
    if (node.right == null) return dfs(node.left) + 1;
    return Math.min(dfs(node.left), dfs(node.right)) + 1;
  };

  return dfs(root);
};

如何判断二叉树是否平衡？

• 定义: 任一节点的左右子树高度差都不超过 1;
• 优化: 让递归同时完成求高度与判平衡, 一旦不平衡就返回 -1 提前终止;

const isBalanced = function (root) {
  const dfs = (node) => {
    if (node == null) return 0;
    const left = dfs(node.left);
    const right = dfs(node.right);
    if (left === -1 || right === -1 || Math.abs(left - right) > 1) return -1;
    return Math.max(left, right) + 1;
  };

  return dfs(root) !== -1;
};

如何求二叉树的直径？

• 定义: 任意两节点之间最长路径的边数;
• 关键: 直径可能不经过根节点, 必须对每个节点计算 "左高 + 右高" 并取最大值;
• 返回值: 向父节点返回单侧最大高度, 而不是直径本身;

const diameterOfBinaryTree = function (root) {
  let res = 0;
  const dfs = (node) => {
    if (node == null) return 0;
    const left = dfs(node.left);
    const right = dfs(node.right);
    res = Math.max(res, left + right);
    return Math.max(left, right) + 1;
  };
  dfs(root);
  return res;
};

如何求二叉树的最大路径和？

• 定义: 任意节点序列 (不要求经过根) 的节点值之和的最大值;
• 贡献值: 单侧子树的贡献取 max(子树贡献, 0), 负贡献直接舍弃;
• 更新: 经过当前节点的路径和 = 左贡献 + 右贡献 + 当前值; 返回给父节点的是 当前值 + max(左贡献, 右贡献);

const maxPathSum = function (root) {
  let res = -Infinity;
  const dfs = (node) => {
    if (node == null) return 0;
    const left = Math.max(dfs(node.left), 0);
    const right = Math.max(dfs(node.right), 0);
    res = Math.max(res, left + right + node.val);
    return node.val + Math.max(left, right);
  };
  dfs(root);
  return res;
};

• 复杂度: 以上各题均为时间 O(n), 空间 O(n) 递归栈;
• 与直径的关系: 直径统计边数, 最大路径和统计权值和, 骨架相同, 只是聚合内容不同;