Java通过值和递归

Question

我有简单的代码打印路径到树中的特定节点。用java字符串我的FPGA实现是如下

//using strings 
public static void getPathS(Node node,String path,int key){ 
    if (node == null) { 
     return; 
    } else if(node.data == key) { 
     System.out.println(path+" "+key);; 
    } 

    getPathS(node.left,path+" "+node.data,key); 
    getPathS(node.right,path+" "+node.data,key); 
} 

假设有树下面给，

如果我呼吁3的getPaths，上面的实现将打印

1 34 3 //path from root to the element 

如果我用下面的ArrayList实现相同的方法

public static List getPath(Node node, List<Integer> path, int key) { 
    if (node == null) { 
     //1 . path = new ArrayList<Integer>(); 
     path = new ArrayList<Integer>(); 
     // 2. or tried path.clear() -- it should clear the path 
     //return path; 
     return null; 
    } else if (node.data == key) { 
     path.add(node.data); 
     return path; 
    } 

    path.add(node.data); 
    return nonNull(getPath(node.left, path, key), getPath(node.right, path, key)); 
} 

private List nonNull(List path1, List path2) { 
    if (path1 != null) 
     return path1; 
    if(path2 !=null) 
     return path2; 
    return null; 
} 

// class Node { Node left, Node right , int data; }; 
//Code to call getPath 
Node node = new Node(1); 
node.left = new Node(2); 
node.left.left = new Node(4); 
node.right = new Node(34); 
node.right.right = new Node(3); 
System.out.println(getPath(node, new ArrayList(), 3)); 

在第二实现中，我尝试了两种方法，当我们得到空节点，在第一次的方法，如果我给你新ArrayList到路径，它打印的所有元素，即

[1, 2, 4, 34, 3] 

如果我使用path.clear()，只有它打印最后一个元素，即要搜索的元素。

我们如何确保ArrayList在递归中以String方式工作？

Answer 1

这里的问题是，你不认为你的电话nonNull()与两个分支失败。 这是一个修正，考虑到这种可能性，并且如果我们未能在其子节点中找到该键，则删除当前节点的数据。

public static List<Integer> getPath(Node node, List<Integer> path, int key) { 
    if (node == null) { 
     return null; 
    } else if (node.data == key) { 
     path.add(node.data); 
     return path; 
    } 
    path.add(node.data); 

    // path is unchanged if nothing is found in left children 
    if (getPath(node.left, path, key) != null || getPath(node.right, path, key) != null) { 
     // found in one branch or the other 
     return path; 
    } 

    // not found in either branch, remove our data 
    path.remove(path.size() - 1); 
    return null; 
} 

当然，它看起来像我们操纵不同的名单，但只能有一个：作为参数提供的第一次一个。这就是为什么数据应该从中删除。你需要清楚你的论点。

---

一个更干净的解决方案，强调只有一个列表的事实。

/** 
* Appends to the specified list all keys from {@code node} to the {@link Node} containing the 
* specified {@code key}. If the key is not found in the specified node's children, the list is 
* guaranteed to be unchanged. If the key is found among the children, then the specified list 
* will contain the new elements (in addition to the old ones). 
* 
* @param node 
*   the node to start at 
* @param path 
*   the current path to append data to 
* @param key 
*   the key to stop at 
* @return true if the key was found among the specified node's children, false otherwise 
*/ 
public static boolean getPath(Node node, List<Integer> path, int key) { 
    if (node == null) { 
     // leaf reached, and the key was not found 
     return false; 
    } 

    // add data to the path 
    path.add(node.data); 

    // the OR is lazy here, so we treat everything in the given order 
    // if getPath failed on the left children, path is unchanged and used for right children 
    if (node.data == key || getPath(node.left, path, key) || getPath(node.right, path, key)) { 
     // the key is found in the current node, its left children, or its right children 
     return true; 
    } 

    // not found in either branch, remove our data 
    path.remove(path.size() - 1); 
    return false; 
} 

请注意，我没有使用path.remove(node.data)，因为有可能是与该数据更是一个节点，第一个将被删除，而不是最后一次。