algorithm - 在线性时间内为树中的每个节点找到最左边的 child ？

Question

A paper我正在阅读声称

It is easy to see that there is a linear time algorithm to compute the function l()

其中 l() 给出最左边的 child (输入和输出都在树的后序遍历中)。但是，我只能想到一个天真的 O(n^2) 实现，其中 n 是树中的节点数。

例如，考虑以下树:

  a
 / \
c   b

在后序遍历中，树是c b a。相应的函数l()应该给出c b c。

这是我在 O(n^2) 时间内实现的。

public Object[] computeFunctionL(){
    ArrayList<String> l= new ArrayList<String>();
    l= l(this, l);
    return l.toArray();
}

private ArrayList<String> l(Node currentRoot, ArrayList<String> l){
    for (int i= 0; i < currentRoot.children.size(); i++){
        l= l(currentRoot.children.get(i), l);
    }
    while(currentRoot.children.size() != 0){
        currentRoot= currentRoot.children.get(0);
    }
    l.add(currentRoot.label);
    return l;
}

树是这样制作的:

public class Node {
private String label;
private ArrayList<Node> children= new ArrayList<Node>();
...

Answer 1

您可以使用一种简单的递归算法，可以在每个节点的 O(1) 时间内计算此信息。由于总共有 n 个节点，这将在 O(n) 总时间内运行。

基本思想是以下递归见解:

• 对于任何没有左 child 的节点 n，l(n) = n。
• 否则，如果 n 有 child L，则 l(n) = l(L)。

这产生了这个递归算法，它用它的 l 值注释每个节点:

function computeL(node n) {
   if n is null, return.

   computeL(n.left)
   computeL(n.right)

   if n has no left child:
      set n.l = n
   else
      set n.l = n.left.l

希望这对您有所帮助!