Печать всех путей двоичного дерева

Question

Я работаю над проблемой для печати всех путей двоичного дерева, и это дает результат. Создать глобальный переменную ЕО, а также в рекурсии printAllRootToLeafPaths метод, строковая переменная путь используются. Есть ли какой-нибудь способ, которым я могу сделать 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; 
    } 

} 

Как вы можете видеть, что вам нужно только путь строка внутри печатьAllRootToLeafPaths. Однако эта функция получила два параметра. Вы можете заменить второй параметр для глобальной переменной, но с рекурсией ее сложнее поддерживать.

Результат этого кода:

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