18

我正在尝试使用 java 在二叉树中打印所有根到叶路径。

public void printAllRootToLeafPaths(Node node,ArrayList path) 
{
    if(node==null)
    {
        return;
    }
    path.add(node.data);

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

在主要方法中：

 bst.printAllRootToLeafPaths(root, new ArrayList());

但它给出了错误的输出。

给定树：

   5
  / \
 /   \
1     8
 \    /\
  \  /  \
  3  6   9

预期输出：

[5, 1, 3]

[5, 8, 6]

[5、8、9]

但是输出产生了：

[5, 1, 3]

[5、1、3、8、6]

[5、1、3、8、6、9]

有没有人能看出来...

4

12 回答 12

29

调用递归方法：

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

当您传递path( 而不是new ArrayList(path)在所有方法调用中使用单个对象时，会发生什么，这意味着，当您返回原始调用者时，该对象的状态与原来不同。

您只需要创建一个新对象并将其初始化为原始值。这样原始对象就不会被修改。

于 2013-02-18T12:58:40.253 回答
10 
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)是关键，它会在打印相应的路径后删除元素

于 2013-06-25T18:10:37.773 回答
9

您正在递归地传递您的列表，但这是一个可变对象，因此所有调用都会修改它（通过调用List.add）并破坏您的结果。尝试将参数克隆/复制path到所有递归调用，以便为每个分支 (harhar) 提供自己的上下文。

于 2013-02-18T12:56:51.343 回答
4

你也可以这样做。这是我的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);
}
于 2016-06-29T09:00:32.717 回答
3

这是正确的实现

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
于 2016-02-18T10:01:39.933 回答
1

这是我的解决方案：一旦我们遍历左或右路径，只需删除最后一个元素。

代码：

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

    }
}
于 2019-09-04T02:07:04.837 回答
0 
/* 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's 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("");
}
于 2016-09-06T16:20:45.677 回答
0

我用 an 尝试了这个问题，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);
}
于 2017-01-17T09:41:14.610 回答
0

我们可以使用递归来实现它。正确的数据结构使其简洁高效。 

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;


}
于 2017-06-20T02:05:25.877 回答
0

您可以执行以下操作，

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;

}
于 2019-03-22T12:07:50.530 回答
0

这是我将所有路径值存储在 List 中然后打印列表的解决方案

基本上什么代码递归地调用 rootToLeafPaths 方法并将字符串传递给用逗号（“，”）分隔的值。递归函数的基本条件是我们到达叶节点（两个孩子都为空）。那时，我们只是从字符串中提取 int 值并将其存储在 List 中

class Solution {
    public void printBTfromRootToLeaf (TreeNode root) {
        if(root == null) return 0;
        if (root.left == null & root.right == null) return 1;
        List<List<Integer>> res = new ArrayList();
        rootToLeafPaths(root, res, "");
        System.out.println(res);
    }
private void rootToLeafPaths(TreeNode root, List<List<Integer>> res, String curr) {
        if (root.left == null && root.right == null) {
            String[] vals = curr.split(",");
            List<Integer> temp = new ArrayList<>();
            for (String val : vals) temp.add(Integer.parseInt(val));
            temp.add(root.val);
            res.add(new ArrayList<>(temp));
        }
        if (root.left != null) rootToLeafPaths(root.left, res, curr + root.val + ",");
        if (root.right != null) rootToLeafPaths(root.right, res, curr + root.val + ",");
    }
}
于 2020-05-25T05:49:35.793 回答
0

它是用 JS 编写的，但您可以获得逻辑。

function dive(t, res, arr) {
        if(t.value != null && t.value != undefined) {
            res = res ? `${res}->${t.value}`: `${t.value}`;
        }
        if(t.left) {
            dive(t.left, res, arr );
        } 
        if(t.right) {
            dive(t.right, res, arr );
        } 
        if(!t.left && !t.right) {
            console.log(res)
            arr.push(res);
            return;
        }
}

function getPaths(t) {
    let arr = [];
    if(!t.left && !t.right) {
        t.value != null && t.value != undefined && arr.push(`${t.value}`);
        console.log(arr)
        return arr;
    }
    dive(t, null, arr);
    console.log(arr)
}


//INPUT
const x = {
    value: 5,
    left: {
        value: 4,
        left: {
            value: 3,
            left: {
                value: 2,
                left: {
                    value: 1,
                    left: {
                        value: 0
                    },
                    right: {
                        value: 1.5
                    }
                },
                right: {
                    value: 2.5
                }
            },
            right: {
                value: 3.5
            }
        },
        right: {
            value: 4.5,
            right: {
                value: 4.8
            }
        }
    },
    right: {
        value: 8,
        left: {
            value: 7
        }
    }
}

getPaths(x);

//OUTPUT

[ '5->4->3->2->1->0',
  '5->4->3->2->1->1.5',
  '5->4->3->2->2.5',
  '5->4->3->3.5',
  '5->4->4.5->4.8',
  '5->8->7' ]
于 2020-06-26T18:12:27.707 回答