Распечатать все корневые пути листьев в двоичном дереве

Ответ 1

Вызвать рекурсивные методы с помощью:

printAllRootToLeafPaths(node.left, new ArrayList(path));
printAllRootToLeafPaths(node.right, new ArrayList(path));

Что происходит, когда вы передаете path (вместо new ArrayList(path)), вы используете один объект во всех вызовах методов, что означает, что при возврате к исходному вызывающему объекту объект не находится в том же как это было.

Вам просто нужно создать новый объект и инициализировать его исходными значениями. Таким образом, исходный объект не изменяется.

Ответ 2

Вы передаете свой рекурсивный рекурсивно, но это изменчивый объект, поэтому все вызовы будут его изменять (вызывая List.add) и искажая результаты. Попробуйте клонировать/копировать аргумент path ко всем рекурсивным вызовам, чтобы обеспечить каждую ветвь (harhar) своим собственным контекстом.

Ответ 3

public void PrintAllPossiblePath(Node node,List<Node> nodelist)
{
    if(node != null)
    {
            nodelist.add(node);
            if(node.left != null)
            {
                PrintAllPossiblePath(node.left,nodelist);
            }
            if(node.right != null)
            {
                PrintAllPossiblePath(node.right,nodelist);
            }
            else if(node.left == null && node.right == null)
            {

            for(int i=0;i<nodelist.size();i++)
            {
                System.out.print(nodelist.get(i)._Value);
            }
            System.out.println();
            }
            nodelist.remove(node);
    }
}

nodelist.remove(node) - это ключ, он удаляет элемент, когда он печатает соответствующий путь

Ответ 4

Вот правильная реализация

public static <T extends Comparable<? super T>> List<List<T>> printAllPaths(BinaryTreeNode<T> node) {
    List <List<T>> paths = new ArrayList<List<T>>();
    doPrintAllPaths(node, paths, new ArrayList<T>());
    return paths;
}

private static <T extends Comparable<? super T>> void doPrintAllPaths(BinaryTreeNode<T> node, List<List<T>> allPaths, List<T> path) {
    if (node == null) {
        return ;
    }
    path.add(node.getData());
    if (node.isLeafNode()) {
        allPaths.add(new ArrayList<T>(path));   

    } else {
        doPrintAllPaths(node.getLeft(), allPaths, path);
        doPrintAllPaths(node.getRight(), allPaths, path);
    }
    path.remove(node.getData());
}

Вот тестовый пример

@Test
public void printAllPaths() {
    BinaryTreeNode<Integer> bt = BinaryTreeUtil.<Integer>fromInAndPostOrder(new Integer[]{4,2,5,6,1,7,3}, new Integer[]{4,6,5,2,7,3,1});
    List <List<Integer>> paths = BinaryTreeUtil.printAllPaths(bt);

    assertThat(paths.get(0).toArray(new Integer[0]), equalTo(new Integer[]{1, 2, 4}));
    assertThat(paths.get(1).toArray(new Integer[0]), equalTo(new Integer[]{1, 2, 5, 6}));
    assertThat(paths.get(2).toArray(new Integer[0]), equalTo(new Integer[]{1, 3, 7}));

    for (List<Integer> list : paths) {          
        for (Integer integer : list) {
            System.out.print(String.format(" %d", integer));
        }
        System.out.println();
    }
}

Вот вывод

1 2 4

1 2 5 6

1 3 7

Ответ 5

вы также можете сделать это. вот мой код Java.

public void printPaths(Node r,ArrayList arr)
{
    if(r==null)
    {
        return;
    }
    arr.add(r.data);
    if(r.left==null && r.right==null)
    {
        printlnArray(arr);
    }
    else
    {
        printPaths(r.left,arr);
        printPaths(r.right,arr);
    }

     arr.remove(arr.size()-1);
}

Ответ 6

/* Given a binary tree, print out all of its root-to-leaf
   paths, one per line. Uses a recursive helper to do the work.*/
void printPaths(Node node) 
{
    int path[] = new int[1000];
    printPathsRecur(node, path, 0);
}

/* Recursive helper function -- given a node, and an array containing
   the path from the root node up to but not including this node,
   print out all the root-leaf paths. */
void printPathsRecur(Node node, int path[], int pathLen) 
{
    if (node == null)
        return;

    /* append this node to the path array */
    path[pathLen] = node.data;
    pathLen++;

    /* it a leaf, so print the path that led to here */
    if (node.left == null && node.right == null)
        printArray(path, pathLen);
    else
        { 
        /* otherwise try both subtrees */
        printPathsRecur(node.left, path, pathLen);
        printPathsRecur(node.right, path, pathLen);
    }
}

/* Utility that prints out an array on a line */
void printArray(int ints[], int len) 
{
    int i;
    for (i = 0; i < len; i++) 
        System.out.print(ints[i] + " ");
    System.out.println("");
}

Ответ 7

Я пробовал эту проблему с ArrayList, а моя программа печатала аналогичные пути.

Итак, я изменил свою логику, чтобы правильно работать, поддерживая внутренний count, вот как я это сделал.

private void printPaths(BinaryNode node, List<Integer> paths, int endIndex) {
        if (node == null)
            return;
        paths.add(endIndex, node.data);
        endIndex++;
        if (node.left == null && node.right == null) {
            //found the leaf node, print this path
            printPathList(paths, endIndex);
        } else {
            printPaths(node.left, paths, endIndex);
            printPaths(node.right, paths, endIndex);
        }
    }

public void printPaths() {
    List<Integer> paths = new ArrayList<>();
    printPaths(root, paths, 0);
}

Ответ 8

Мы можем использовать рекурсию для ее достижения. Правильная структура данных делает ее кратким и эффективным.

List<LinkedList<Tree>> printPath(Tree root){

    if(root==null)return null;

    List<LinkedList<Tree>> leftPath= printPath(root.left);
    List<LinkedList<Tree>> rightPath= printPath(root.right);

    for(LinkedList<Tree> t: leftPath){
         t.addFirst(root);
    }
    for(LinkedList<Tree> t: rightPath){
         t.addFirst(root);
    }


 leftPath.addAll(rightPath);

 return leftPath;


}

Ответ 9

Вы можете сделать следующее,

public static void printTreePaths(Node<Integer> node) {
    int treeHeight = treeHeight(node);
    int[] path = new int[treeHeight];
    printTreePathsRec(node, path, 0);

}

private static void printTreePathsRec(Node<Integer> node, int[] path, int pathSize) {
    if (node == null) {
        return;
    }

    path[pathSize++] = node.data;

    if (node.left == null & node.right == null) {
        for (int j = 0; j < pathSize; j++ ) {
            System.out.print(path[j] + " ");
        }
        System.out.println();
    }

     printTreePathsRec(node.left, path, pathSize);
     printTreePathsRec(node.right, path, pathSize);
}

public static int treeHeight(Node<Integer> root) {
    if (root == null) {
        return 0;
    }

    if (root.left != null) {
        treeHeight(root.left);
    }

    if (root.right != null) {
        treeHeight(root.right);
    }

    return Math.max(treeHeight(root.left), treeHeight(root.right)) + 1;

}

Ответ 10

Вот мое решение: Как только мы пройдем по левому или правому пути, просто удалим последний элемент.

Код:

public static void printPath(TreeNode root, ArrayList list) {

    if(root==null)
        return;

    list.add(root.data);

    if(root.left==null && root.right==null) {
        System.out.println(list);
        return;
    }
    else {
        printPath(root.left,list);
        list.remove(list.size()-1);

        printPath(root.right,list);
        list.remove(list.size()-1);

    }
}