树中下降路径的最大长度始终向左
我正在准备技术面试，所以基本上从一开始就学习算法:)我们给了一个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 。
非递归解决方案
实际上，这是我测试的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 toProcess = new List (10000); if (T == null) return 0; int maxLength = 0; Tx = 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.lx = 1 + reminder; maxLength = Math.Max(maxLength, currNode.lx); toProcess.Add(currNode.l); } if (currNode.r != null) { currNode.rx = 100000 + (currNode.x - reminder); maxLength = Math.Max(maxLength, currNode.rx / 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 toProcess = new List (10000); int rightmask = 0x0000FFFF; int leftmask = ~0x0000FFFF; if (T == null) return 0; int maxLength = 0; Tx = 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.lx = newLength << 16; maxLength = Math.Max(maxLength, newLength); toProcess.Add(currNode.l); } if (currNode.r != null) { int rightpart = (currNode.x & rightmask); currNode.rx = 1 + rightpart; maxLength = Math.Max(maxLength, currNode.rx); 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节点的二叉树进行测试：
公共类Node {
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)); }
}
公共类Main {
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 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); }