在二叉树中打印所有根到叶子路径
我试图使用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]
有人可以搞清楚……
使用以下命令调用递归方法：
printAllRootToLeafPaths(node.left, new ArrayList(path)); printAllRootToLeafPaths(node.right, new ArrayList(path));
当你传递path （而不是new ArrayList(path) ，你会在所有方法调用中使用单个对象，这意味着，当你返回到原始调用者时，该对象与它的状态不同是。
您只需创建一个新对象并将其初始化为原始值。 这样原始对象就不会被修改。
你递归地传递你的列表，但这是一个可变对象，所以所有的调用都会修改它（通过调用List.add ）并破坏你的结果。 尝试将path参数克隆/复制到所有递归调用，以便为每个分支（harhar）提供自己的上下文。
public void PrintAllPossiblePath(Node node,List 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.remove(node)是键，它在打印相应路径后删除该元素
你也可以这样做。 这是我的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); }
这是正确的实施
public static > List> printAllPaths(BinaryTreeNode node) { List > paths = new ArrayList>(); doPrintAllPaths(node, paths, new ArrayList ()); return paths; } private static > void doPrintAllPaths(BinaryTreeNode node, List> allPaths, List path) { if (node == null) { return ; } path.add(node.getData()); if (node.isLeafNode()) { allPaths.add(new ArrayList (path)); } else { doPrintAllPaths(node.getLeft(), allPaths, path); doPrintAllPaths(node.getRight(), allPaths, path); } path.remove(node.getData()); }
这是测试用例
@Test public void printAllPaths() { BinaryTreeNode bt = BinaryTreeUtil. fromInAndPostOrder(new Integer[]{4,2,5,6,1,7,3}, new Integer[]{4,6,5,2,7,3,1}); List > 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 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
/* 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(""); }
我用ArrayList尝试了这个问题，我的程序打印了类似的路径。
所以我通过维护内部count来修改我的逻辑以正常工作，这就是我如何做到的。
private void printPaths(BinaryNode node, List 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 paths = new ArrayList<>(); printPaths(root, paths, 0); }
我们可以使用递归来实现它。 正确的数据结构使其简洁高效。
List> printPath(Tree root){ if(root==null)return null; List> leftPath= printPath(root.left); List> rightPath= printPath(root.right); for(LinkedList t: leftPath){ t.addFirst(root); } for(LinkedList t: rightPath){ t.addFirst(root); } leftPath.addAll(rightPath); return leftPath; }