代码之家 › 专栏 › 技术社区 › ABGR

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

binary-tree recursion algorithm javascript

ABGR · 技术社区 · 10 月前

所以我正在努力 problem :

给定二叉树的根,返回树直径的长度。

二叉树的直径是树中任意两个节点之间最长路径的长度。此路径可能穿过根,也可能不穿过根。

两个节点之间的路径长度由它们之间的边数表示。

以下是我试图解决的问题:

var diameterOfBinaryTree = function(root) {

  if (root === null) return 0;
  let max_height = 0;

  function maxDepth(node) {
    if (node === null) return 0;
    var lh = maxDepth(node.left);
    var rh = maxDepth(node.right);

    return 1 + Math.max(lh, rh);
  }

  max_height = Math.max(max_height, maxDepth(root.left) + maxDepth(root.right));

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

  return max_height
}

现在,除了最长路径不通过根节点的情况外,这确实有效。但我确实尝试将这些情况合并,即我确实在树的每个节点上迭代:

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

我哪里做错了?感谢任何帮助。请注意,我确实需要将其从O(N2)优化到O(N),但现在我只是在尝试蛮力。

它失败的测试用例是这棵树:

考虑从-1到-2的最长路径

2 回复 | 直到 10 月前

ruakh 10 月前

但我确实尝试将这些情况合并,即我确实在树的每个节点上迭代:
diameterOfBinaryTree(root.left);
diameterOfBinaryTree(root.right);
我哪里做错了?

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

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

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

-1

deep206 10 月前

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

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;
}