java打印二叉树的所有路径

Question

我正在解决一个问题，打印二叉树的所有路径，这会给出结果。我创建了一个全局变量sw，并且在printAllRootToLeafPaths方法的递归中，使用了一个字符串变量path。是否有某种方法可以仅在printAllRootToLeafPaths方法中生成sw和路径？因此，方法如下所示

public static ArrayList<String> printAllRootToLeafPaths(TreeNode node ){

   /*
      String path and ArrayList<String> sw will be initiated here 
   */
}

==============================================================================

import java.io.*;
import  java.util.*; 

class TreeNode {

      int val;
      TreeNode left;
      TreeNode right;

      TreeNode(int x) { 
        val = x; 
    }
}


public class myTest {



    public static ArrayList<String> sw = new ArrayList<String>(); 

    public static void main ( String[] args ){

        TreeNode root = new TreeNode( 1 );

        root.left= new TreeNode( 2 ) ;
        root.left.left =  new TreeNode( 5 );

        root.right =  new TreeNode(3);


        sw =  printAllRootToLeafPaths( root, new String() ); 
        String[] result =  new String[ sw.size() ]; 
        int count =  0 ; 

        for ( String s: sw ){

            result[count] = '"'+ s + '"'; 
            count++; 
        }

        System.out.println( Arrays.toString( result ) );

    }


    public static ArrayList<String> printAllRootToLeafPaths(TreeNode node, String path ) {

        if( node==null ) return null ; 

        path += String.valueOf(node.val)+ "->"; 

        if( node.left == null && node.right == null ){

            String my = path.substring(0, path.length() -2 ); 
            sw.add( my );

            // optional 
            path = ""; 
        }

        else {

            printAllRootToLeafPaths( node.left, new String (path) );
            printAllRootToLeafPaths( node.right, new String (path)  );
        }  

        return sw ;     
    }

}

Answer 1

请查看此解决方案：

class TreeNode {

    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}
public class myTest {

    public static void main(String[] args) {

        TreeNode root = new TreeNode(1);

        root.left = new TreeNode(2);
        root.left.left = new TreeNode(5);

        root.right = new TreeNode(3);

        printAllRootToLeafPaths(root, new String());

    }

    public static void printAllRootToLeafPaths(TreeNode node, String path) {
        path = path + " -> " + node.val;
        if (isLeaf(node)) {

            System.out.println(path);
        } else if (node.left == null && node.right != null) {
            printAllRootToLeafPaths(node.right, path);
        } else if (node.left != null && node.right == null) {
            printAllRootToLeafPaths(node.left, path);
        } else {
            printAllRootToLeafPaths(node.left, path);
            printAllRootToLeafPaths(node.right, path);
        }

    }

    public static boolean isLeaf(TreeNode t) {
        if (t.left == null && t.right == null) {
            return true;
        }
        return false;
    }

}

如您所见，您只需要printallRootToLeafpath中的路径字符串。然而，这个函数有两个参数。可以替换全局变量的第二个参数，但使用递归更难维护

该代码的结果是：

-> 1 -> 2 -> 5
-> 1 -> 3

Answer 2

  public static List<String> printAllRootToLeafPaths(TreeNode node ){

       /*
          String path and ArrayList<String> sw will be initiated here 
       */
     List<String> sw =new ArrayList<String>();
     StringBuilder path=new StringBuilder();
     printAllRootToLeafPaths(TreeNode node,path,sw ) ;
    }

如果不是静态的，则下面的函数需要在每次调用中传递对列表的引用

   public static List<String> printAllRootToLeafPaths(TreeNode node, StringBuilder path,List<String> pathList ) 
    {
     ...
    else {
           printAllRootToLeafPaths( node.left, new StringBuilder (path.toString()),pathList );
           printAllRootToLeafPaths( node.right, new StringBuilder (path.toString()),pathList  );
            }  

Answer 3

sw =   printAllRootToLeafPaths(node.left, new String());
sw =   printAllRootToLeafPaths(node.right, new String());

当您传递路径（而不是new String()）时，是指在所有方法调用中使用单个对象，这意味着，当您返回到原始调用方时，对象的状态与以前不同。然后调用递归方法