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)，因爲有可能是與該數據更是一個節點，第一個將被刪除，而不是最後一次。