递归找到二叉树中节点的路径

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

我看了看你的​​方法，我实际上没有看到任何明显的问题吧。