javascript - 如何使用Javascript在二分搜索树中找到最长的路径？

我试图找出如何在二进制搜索树中找到最长的路径（对bst和递归没有真正的经验），并找到了我根本不理解的解决方案。

const height = (node) => {
  if(!node) return 0;
  var leftHeight = height(node.left);
  var rightHeight = height(node.right);
  return Math.max(leftHeight, rightHeight) + 1;
}
height(node)

柜台在哪里？如我所见，在leftHeight和rightHeight中将存储最后一个值。不计算每个值怎么可能计数呢？
我实际在哪里返回值？我返回最终结果-> Math.max（leftHeight，rightHeight），但是在每个递归调用中我应在哪里添加，保存和返回值？


一个解释真是太神奇了！谢谢！

最佳答案

基本上在某些时候，您的调用栈将是最长的路径。

因此，让我们看一下这棵树：

  A
 / \
B   C
   / \
  D   E

这里是JS：

{
    name: 'A'
    left: {
        name: 'B',
        left: null,
        right: null,
    }
    right: {
        name: 'C',
        left: {
            name: 'D',
            left: null,
            right: null,
        },
        right: {
            name: 'E',
            left: null,
            right: null,
        }
    }
}

然后，您执行node(nodeA)。从现在开始，我将使用nodeX引用节点X的对象。

然后将执行height(node.left);，并且由于node.left是nodeB，因此基本上是height(nodeB)。所以你的调用栈就是这样：

height(nodeA)
height(nodeB)

现在执行height(node.left);（节点现在为nodeB）。并且由于left的nodeB是null，因此本质上是height(nodeB)。那么您的调用栈就是：

height(nodeA)
height(nodeB)
height(null)

现在，行if(!node) return 0;将立即从函数返回，因为node是null，因此!node是true。返回值将为指定的0。

调用堆栈现在又是这个（最后一个堆栈元素已删除）：

height(nodeA)
height(nodeB)

并且值leftHeight现在将为0（因为这就是返回的值）。
行var rightHeight = height(node.right);本质上将执行相同的操作，因为node.right也是null。因此，Math.max(leftHeight, rightHeight)本质上是Math.max(0, 0)，因此为0。此加1是1。这将被退回。调用堆栈现在如下所示：

height(nodeA)

leftHeight的值1是正确的。

现在，右侧也会发生相同的情况，C也是如此。但是，这里node.left不会为空，而是nodeD，因此将构建另一个堆栈框架：

height(nodeA)
height(nodeC)
height(nodeD)

此处nodeD左右为空，将返回1，与nodeB相同。 nodeE也是如此。然后nodeC然后将leftHeight设置为1，将rightHeight设置为1。此加1为2，因此height(nodeC)将返回2。

然后height(nodeA)将leftHeight设为1，将rightHeight设为2。所以Math.max(leftHeight, rightHeight) + 1;是3并且是正确的结果。



基本上，您的代码正在计数，而+1是计数。计数的起点始终是return 0。

关于javascript - 如何使用Javascript在二分搜索树中找到最长的路径？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/52212822/