如何提高递归函数的运行时间

Question

在解决此问题中：http://www.cs.duke.edu/csed/newapt/drawtree.html我编写了下面的代码，但它似乎运行速度太慢。有没有更快的方法检查所有的孩子节点W/O使用FOR循环？队列会有帮助吗？

public class DrawTree { 
    HashMap<String, ArrayList<String>> map = 
      new HashMap<String, ArrayList<String>>(); 
    ArrayList<String> drawing = new ArrayList<String>(); 
    String root; 
    public String[] draw(int[] parents, String[] names) { 


     for(int x=0; x<parents.length; x++) 
     { 
      int parentindex = parents[x]; 
      //root name 

      if(parentindex==-1) 
      { 
       root=names[x]; 
       if(!map.containsKey(names[x])) 
       { 

        map.put(names[x], new ArrayList<String>()); 
       } 

       continue; 
      } 

      //add parent, child to map 
      if (!map.containsKey(names[parentindex])) 
          map.put(names[parentindex], 
            new ArrayList<String>()); 
      map.get(names[parentindex]).add(names[x]); 
     } 


     sketch("",root,false); 
     return drawing.toArray(new String[drawing.size()]); 
     } 
    //***IMPROVE RUN TIME - different algorithm??*** 
    //method takes root and prefix? 
    public void sketch(String parent, String child, boolean addPipe){ 

     StringBuilder toAdd = new StringBuilder(); 


     //don't need to add connector pipe 
     if(!addPipe) 
     { 
      //number of spaces to add to prefix 
      int spaces = parent.indexOf('-')+1; 

      //add spaces to prefix 
      while(spaces>0) 
      { 
       toAdd.append(" "); 
       spaces--; 
      } 
      toAdd.append("+-"+child); 
     } 


     //index of pipe in parent, -1 if parent doesn't have pipe 
     int parentPipe = parent.indexOf('|'); 

     //need to add connector pipe & parent has pipe 
      // (is a child of a subtree) 
     if(parentPipe>0) 
     { 
      //number of spaces to add to prefix 
      int spaces = parent.indexOf('-')+1; 

      //add spaces to prefix 
      while(spaces>0) 
      { 
       if(spaces==parentPipe) toAdd.append('|'); 
       else toAdd.append(" "); 
       spaces--; 
      } 
      toAdd.append("+-"+child); 

     } 

     //need to add pipe and parent doesn't have pipe 
     if(addPipe && parentPipe<0) 
     { 
      int spaces = parent.indexOf('-')+1; 
      while(spaces>0) 
      { 
       if(spaces==2) toAdd.append('|'); 
       else toAdd.append(" "); 
      } 
      toAdd.append("+-"+child); 
     } 

     //add child to list of tree drawing 
     String node = toAdd.toString(); 
     drawing.add(node); 
     //System.out.println(node);  

     //loop through list of children, passing each recursively 
      //...count level? 
     if(map.containsKey(child)) 
     { 
      //System.out.println("map works"); 
      for(int x = 0; x<map.get(child).size(); x++) 
      { 
       boolean pipe = false; 
       if(x<(map.get(child).size()-1)) pipe=true; 
       //System.out.println(map.get(child).get(x)); 
       sketch(node, map.get(child).get(x), pipe); 
      } 
     } 

    } 

Answer 1

我不认为队列在这种情况下会有帮助。 For循环可能是这样做的方式

public class DrawTree { 
    public String[] lines; 
    public int lineNum; 

    public String[] draw(int[] parents, String[] names) { 
     lines = new String[parents.length]; 
     lineNum = 0; 
     drawLeaf(parents, names, -1, 0); 
     return lines; 
    } 

    public void drawLeaf(int[] parents, String[] names, int root, int depth) { 
     for (int i = 0; i < parents.length; i++) { 
      if (parents[i] == root) { 
       lines[lineNum] = ""; 
       for (int j = 0; j < depth; j++) { 
        lines[lineNum] += " "; 
       } 

       lines[lineNum] += "+-" + names[i]; 
       int pipeNum = lineNum - 1; 
       while ((pipeNum >= 0) 
         && (lines[pipeNum].charAt(depth * 2) == ' ')) { 
        String oldLeaf = lines[pipeNum]; 
        lines[pipeNum] = ""; 
        for (int j = 0; j < oldLeaf.length(); j++) { 
         if (j == depth * 2) { 
          lines[pipeNum] += '|'; 
         } else { 
          lines[pipeNum] += oldLeaf.charAt(j); 
         } 
        } 
        pipeNum--; 
       } 

       lineNum++; 
       drawLeaf(parents, names, i, 1 + depth); 
      } 
     } 
    } 
}