java - 总是向左|向右的树中下降路径的最大长度

Question

我正在准备技术面试，所以基本上是从头开始学习算法:) 我们得到了 BST。我需要在其中找到 desc 路径的最大长度，它总是向左或向右 也就是说，一个示例树的下降路径是2，即15-10-6

   5
  / \
2     15
     /
    10
   / \ 
  6   14

我对算法问题很陌生。解决这个问题的步骤是什么？

我的想法是使用 DFS 和一个计数器来存储最长路径。 但我不知道如何使用递归来完成这项工作，而递归对于这种数据结构来说似乎更自然。

有什么建议/方向吗？

Answer 1

措辞有点困惑，但我认为你的意思是最大值

• 从任何节点开始然后只向左移动的路径的最大长度，或者
• 从任何节点开始然后只向右移动的路径的最大长度。

您分两次执行此操作，一次寻找最大左侧路径，一次寻找最大右侧路径(然后取这两个路径中的最大值)。或者，您可以一次性完成这两项操作。

对于每个节点，您想知道三个值:

1. 从该节点开始的左路径的长度，
2. 从该节点开始的正确路径的长度，以及
3. 从该节点或其后代之一开始的最长路径的长度。

如果您递归执行此操作，这意味着递归应该返回这三个值，可能作为一个小数组或作为一个简单的三字段对象。

这看起来像

Results calculate(Tree node) {
    if (node == null) return new Results(0,0,0);
    else {
        Results leftResults = calculate(node.left);
        Results rightResults = calculate(node.right);
        int leftLength = 1 + leftResults.leftLength;
        int rightLength = 1 + rightResults.rightLength;
        int maxLength = Math.max(Math.max(leftLength, rightLength), 
                                 Math.max(leftResults.maxLength, rightResults.maxLength));
        return new Results(leftLength, rightLength, maxLength);
    }
}

整体结果将只是calculate(root).maxLength。