问题是如何在给定其祖先矩阵的情况下创建二叉树。我在 http://www.ritambhara.in/build-binary-tree-from-ancestor-matrics/ 找到了一个很酷的解决方案.问题是它涉及从矩阵中删除行和列。现在我该怎么做?有人可以为此建议一个伪代码吗?或者,是否有更好的算法?
最佳答案
您不必真正删除行和列。您可以在一些额外的数组中将它们标记为已删除,或者您可以将它们全部设为零,我认为这实际上是相同的(实际上,您仍然需要知道它们已被删除,所以您不选择它们再次在步骤 4.c 中 - 因此,将节点标记为已删除应该就足够了)。
以下是对页面伪代码的修改:
4.b.
used[temp] = true;
for (i = 0 to N)
Sum[i] -= matrix[i][temp]; (aka decrement sum if temp is a predecessor of i)
matrix[i][temp] = 0;
4.c.查找 Sum[i] == 0 和 used[i] == false 的所有行。
关于algorithm - 从祖先矩阵创建二叉树,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/12929829/