遞歸找到二叉樹中節點的路徑

Question

我知道正在搜索的節點位於未排序的二叉樹中，但我無法弄清楚如何通過遞歸調用回傳路徑。我的兩個功能：一個找到特定節點的路徑，另一個返回所有節點的路徑字符串。 0表示左側路徑，右側1路。

private static String getAllPaths(final BinaryNodeInterface<Character> root) 
{ 
    // TO DO 
    String path = ""; 
    String returnStr = ""; 
    return getAP(root, path, returnStr); 
} 

private static String getAP(BinaryNodeInterface<Character> root, String path, 
     String returnStr) 
{ 
    returnStr += "" + root.getData() + " " + path + "\n"; 
    if(root.hasLeftChild()) 
     getAP(root.getLeftChild(), path.concat("0"), returnStr); 
    if(root.hasRightChild()) 
     getAP(root.getRightChild(), path.concat("1"), returnStr); 

    return returnStr; 
} 

private static String getPathTo(final BinaryNodeInterface<Character> root, char c) 
{ 
    // TO DO 
    String path = ""; 
    if(root.getData() == c) 
     return path; 

    if(root.hasLeftChild()) 
    { 
     String s = getPathTo(root.getLeftChild(), c); 

     if(s != null) 
     { 
      path += "0"; 
      path += s; 
      return path; 
     } 
    } 

    if(root.hasRightChild()) 
    { 
     String s = getPathTo(root.getRightChild(), c); 

     if(s != null) 
     { 
      path += "1"; 
      path += s; 
      return path; 
     } 
    } 

    return null; 
} 

我在遞歸方面很糟糕，所以任何幫助都非常感謝。我完成了所有的工作。上面的代碼現在很好。謝謝您的幫助。

Answer 1

字符串在java中是不可變的。當您將String傳遞給方法時，會創建一個全新的值。例如：

void modifyString(String x) { 
    x += "(modified)"; 
} 

如果使用方法：

String s = "myString!"; 
modifyString(s); 
// what does s equal? 

你可能期望s == "myString!(modified)"，但事實卻並非如此。

在你的情況下，你傳遞returnStr作爲參數遞歸調用getAP。但是，它不會按照您的假設進行修改。要修復它，請將遞歸方法調用的結果附加到本地returnStr並返回。

// removed returnStr as a parameter 
private static String getAP(BinaryNodeInterface<Character> root, String path) 
{ 
    String returnStr = "" + root.getData() + " " + path + "\n"; 
    if(root.hasLeftChild()) 
     returnStr += getAP(root.getLeftChild(), path.concat("0")); 
    if(root.hasRightChild()) 
     returnStr += getAP(root.getRightChild(), path.concat("1")); 

    return returnStr; 
} 

我看了看你的​​方法，我實際上沒有看到任何明顯的問題吧。