打印二進制樹的所有路徑

Question

我正在處理打印二叉樹的所有路徑的問題，並給出結果。我創建一個全局變量SW以及在printAllRootToLeafPaths正在使用方法，String變量路徑的遞歸。有一些辦法可以讓SW和路徑只有內部printAllRootToLeafPaths方法？所以，該方法將如下所示。

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

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

當你通過的路徑（而不是 new String()

是你使用一個對象的所有方法調用，這意味着，當您返回到原來的調用者，對象是不一樣狀態，因爲它was.Then調用遞歸方法

Answer 2

對此的解決方案來看看：

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; 
    } 

} 

正如你所看到的，你只需要路徑 printAllRootToLeafPaths中的字符串。但是，這個函數有兩個參數。您可以替換全局變量的第二個參數，但遞歸很難維護。

這段代碼的結果是：

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

Answer 3

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 ); 
      }