我正在准备技术面试，所以基本上从一开始就学习算法:)
我们得到了 BST。我需要找到其中 desc 路径的最大长度，该路径总是向左或向右
换句话说，示例树的下降路径是2，即15-10-6
5
/ \
2 15
/
10
/ \
6 14
我对算法问题非常陌生。解决这个问题的步骤是什么？
我的想法是使用 DFS 和计数器来存储最长路径。
但我不知道如何使用递归来完成这项工作，而递归对于这种数据结构来说似乎更自然。
有什么建议/方向吗？
措辞有点令人困惑，但我认为你的意思是最大
- 从任意节点开始然后仅向左延伸的路径的最大长度，或者
- 从任意节点开始然后仅向右的路径的最大长度。
您分两遍执行此操作，一次查找最大左路径，另一次查找最大右路径（然后取这两条路径中的最大值）。或者，您可以一次性完成这两项工作。
对于每个节点，您需要知道三个值：
- 从该节点开始的左路径的长度，
- 从该节点开始的正确路径的长度，以及
- 从该节点或其子节点之一开始的最长路径的长度。
如果您以递归方式执行此操作，这意味着递归应返回这三个值，可能作为一个小数组或作为一个简单的三字段对象。
这看起来像
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.
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
