我正在为技术面试做准备，所以基本上从一开始就学习算法:) 我们得到了 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.
实际上，这是我经过测试的可编码性问题。为了讨论它，我只是提到了一个非递归解决方案。
树本身有一个可以修改的值。
我在这里找到了比递归解决方案更好的解决方案，但我没有用 Java 编程，所以我将使用正确算法的 C# 解决方案：
public class Tree
{
public int x;
public Tree l;
public Tree r;
}
class solution
{
public int solution(Tree T)
{
// write your code in C# 5.0 with .NET 4.5 (Mono)
List<Tree> toProcess = new List<Tree>(10000);
if (T == null)
return 0;
int maxLength = 0;
T.x = 0;
toProcess.Add(T);
while (toProcess.Count != 0)
{
Tree currNode = toProcess[toProcess.Count-1];
toProcess.RemoveAt(toProcess.Count - 1);
int remainder = currNode.x % 100000;
if (currNode.l != null)
{
currNode.l.x = 1 + remainder;
maxLength = Math.Max(maxLength, currNode.l.x);
toProcess.Add(currNode.l);
}
if (currNode.r != null)
{
currNode.r.x = 100000 + (currNode.x - remainder);
maxLength = Math.Max(maxLength, currNode.r.x / 100000);
toProcess.Add(currNode.r);
}
}
return maxLength;
}
}
如果你计时的话，这比乘数回避要快。这个想法是在每个节点上，您在子节点中存储更长的长度并将它们附加到列表中（如果需要，您可以使用堆栈）以供稍后处理。您使用 int 来存储计数。Codibility 上的原始问题提到不超过 10 000 个节点，最大深度为 800。
最后一个优化是用二进制移位替换我使用 100000 来分隔左右长度，这会更快，即使用 16 个第一位存储左侧的长度，其余的用于存储右侧的长度，但我没有当我开始使用递归方法时，有足够的时间来做这件事。
编辑：我做了按位的，太糟糕了，我没有时间确保它是正确的并提交它，因为它比递归的快得多：
public int solution(Tree T)
{
// write your code in C# 5.0 with .NET 4.5 (Mono)
List<Tree> toProcess = new List<Tree>(10000);
int rightmask = 0x0000FFFF;
int leftmask = ~0x0000FFFF;
if (T == null)
return 0;
int maxLength = 0;
T.x = 0;
toProcess.Add(T);
while (toProcess.Count != 0)
{
Tree currNode = toProcess[toProcess.Count-1];
toProcess.RemoveAt(toProcess.Count - 1);
if (currNode.l != null)
{
int leftpart = (currNode.x & leftmask) >> 16;
int newLength = 1 + leftpart;
currNode.l.x = newLength << 16;
maxLength = Math.Max(maxLength, newLength);
toProcess.Add(currNode.l);
}
if (currNode.r != null)
{
int rightpart = (currNode.x & rightmask);
currNode.r.x = 1 + rightpart;
maxLength = Math.Max(maxLength, currNode.r.x);
toProcess.Add(currNode.r);
}
}
return maxLength;
}
从节点调用的递归函数v应该返回 3 个值：
1. Maximum descending path which goes always left or always right in subtree rooted in v
2. Maximum length of path which goes always left starting from v
3. Maximum length of path which goes always right starting from v
我们分别称这些值(V1, V2, V3)
显然，对于树中的任何叶子，上述所有值都等于 0。
让我们考虑任何内部节点v。
让(L1, L2, L3)是递归调用的左孩子返回的值v。
让(R1, R2, R3)是对 的右孩子的递归调用返回的值v。
然后v，为了计算(V1, V2, V3)只需要结合从左孩子和右孩子返回的结果：
V2等于L2 + 1如果左孩子存在。否则为0。
V3等于R3 + 1是否存在右孩子。否则为0。
V1等于max(L1, R1, V2, V3)
这是该问题的工作代码。给出一个 11 节点的二叉树进行测试：
公共类节点{
int L = 0;
int R = 0;
Node left = null;
Node right = null;
}
公共类 BTree {
void calculate_paths(Node root) {
if (root.left != null) {
calculate_paths(root.left);
root.L = root.left.L + 1;
}
if (root.right != null) {
calculate_paths(root.right);
root.R = root.right.R + 1;
}
}
int max_paths(Node root) {
int maxL = 0;
int maxR = 0;
if (root.left != null) maxL = max_paths(root.left);
if (root.right != null) maxR = max_paths(root.right);
return Math.max(Math.max(root.L, root.R), Math.max(maxL, maxR));
}
}
公共类主要{
public static void main(String[] args){
System.out.println("Let the challenge begin!");
//create the tree
Node n0 = new Node();
Node n1 = new Node();
Node n2 = new Node();
Node n3 = new Node();
Node n4 = new Node();
Node n5 = new Node();
Node n6 = new Node();
Node n7 = new Node();
Node n8 = new Node();
Node n9 = new Node();
Node n10 = new Node();
n0.right = n1;
n0.left = n7;
n1.left = n2;
n2.left = n3;
n2.right = n4;
n4.right = n5;
n5.right = n6;
n6.left = n9;
n6.right = n10;
n7.left = n8;
BTree Tree = new BTree();
Tree.calculate_paths(n0);
System.out.println(Tree.max_paths(n0));
}
}
Java实现：
// auxiliary method, starts the recursion:
public int height(){
if(root != null) // If not null calculate height
return height(root);
else // height is zero...
return 0;
}
// Gets the job done:
private int height(BinaryTreeNode<T> node){
int right = 0, left = 0;
if (node.getLeftChild() != null) // count and calculate left path height
left= 1+ height(node.getLeftChild());
if (node.getRightChild() != null) // count and calculate right path height
right= 1 + height(node.getRightChild());
return Math.max(left, right);
}