树中下降路径的最大长度总是向左移动

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.

Answer 2

非递归解决方案

实际上,这是我测试的Codibility问题.我只是为了讨论它而提到一个非递归的解决方案.

树本身具有可以修改的值.

我找到了一个比递归解决方案更好的解决方案,但是我不用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 reminder = currNode.x % 100000;
            if (currNode.l != null)
            {
                currNode.l.x = 1 + reminder;
                maxLength = Math.Max(maxLength, currNode.l.x);
                toProcess.Add(currNode.l);
            }
            if (currNode.r != null)
            {
                currNode.r.x = 100000 + (currNode.x - reminder);
                maxLength = Math.Max(maxLength, currNode.r.x / 100000);
                toProcess.Add(currNode.r);
            }
        }
        return maxLength;
    }
}

如果你计时,这比复数更快.想法是在每个节点,您在子节点中存储更长的长度,并将它们附加到列表(您可以使用堆栈,如果您需要)以后处理.您使用int来存储计数.Codibility的最初问题是,节点数不超过10000个,最大深度为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;
    }