主页 / coding / 问题 / 78894002
Accepted
ABGR
Asked: 2024-08-21 02:45:25 +0800 CST

二叉树的直径 - 当最长路径不经过根时，失败的情况

  • 772

所以我正在解决这个问题：

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

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

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

以下是我尝试解决的方法：

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 的最长路径

javascript

2 个回答

  1. Best Answer

    但我确实尝试将这些情况纳入其中，即我在树的每个节点上进行迭代：

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

    我哪里做错了？

    该diameterOfBinaryTree函数执行计算并返回一个值，但它没有任何“副作用”——它实际上什么都不做——所以没有理由调用它并丢弃其结果。这是一件好事！像这样的纯函数更容易推理（对人类和编译器来说都是如此）。但这意味着这些递归调用毫无意义。

    相反，您需要实际使用结果：

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

  2. 您需要从根开始遍历，然后计算当前直径的直径最大值以及所在节点迭代中的左+右的加法。

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

相关问题