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

Question

A paper我正在阅读以下声明

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

其中l()给出最左边的子节点(输入和输出都是树的后序遍历)。但是，我只能想到一个简单的 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)。

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

• 对于任何没有左子节点的节点 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

希望这有帮助!