二叉树的直径——当最长路径不通过根时的失败案例

但我确实尝试将这些情况合并,即我确实在树的每个节点上迭代:

diameterOfBinaryTree(root.left);
diameterOfBinaryTree(root.right);

我哪里做错了?

这个 diameterOfBinaryTree 函数执行计算并返回一个值,但它没有任何“副作用”,实际上并没有 做 任何事情,所以永远没有理由调用它并丢弃它的结果。这是一件好事! Pure functions 像这样更容易推理(对人类和编译器来说都是如此)。但这意味着这些递归调用毫无意义。

相反,你需要实际 使用 结果:

return Math.max(
    maxDepth(root.left) + maxDepth(root.right),
    diameterOfBinaryTree(root.left),
    diameterOfBinaryTree(root.right)
);

您需要从根开始遍历,然后计算当前直径的直径最大值,并在您所在节点的迭代中添加左+右。

function diameterOfBinaryTree(root) {
    let max_height = 0;
    
    function maxDepth(node) {
        if (!node) return 0;// if our node is falsy, means no path anymore, return 0

        // Assign the left  of tree to leftHeight and right of tree to rightHeight
        const leftHeight = maxDepth(node.left); 
        const rightHeight = maxDepth(node.right);

        // take the max of current diameter and combination of left+right (in case path goes through root)
        max_height = Math.max(diameter, leftHeight + rightHeight);
        return Math.max(leftHeight, rightHeight) + 1; // add 1 to go a level above
    }
    maxDepth(root); // begin traversing from root
    return max_height;
}