遍历遍历二进制搜索树

Question

我试图递归遍历BST预购，但我无法使其正常工作。这是我尝试过的：

public String PreOrder() {
    return preOrderStringBuild(root, "");
}

public String preOrderStringBuild(Node root, String preOrderString) {
    if (root == null) {
        return "";
    }

    preOrderString += root.key + " "; 
    preOrderStringBuild(root.left, preOrderString);
    preOrderStringBuild(root.right, preOrderString);            

    return preOrderString;
}

但是这只给了我第一个元素……我在这里做错了什么？

Answer 1

在Java中，方法参数通过按值传递，字符串是不可变。

这意味着这行代码不会更改传递给方法的字符串，而是创建一个新的字符串，该字符串只能在该方法的当前调用中看到：

preOrderString += root.key + " "; 

解决此问题的一种方法是使用类似StringBuilder的mutable字符串类型，而不是String。对可变对象的更改在方法外部可见。

public String preOrderStringBuild(Node root, StringBuilder preOrderString) {
    ...
    preOrderString.append(root.key + " "); // instead of preOrderString = ...
    ...

另一种解决此问题的方法是，确保使用递归调用返回的值。通过这条路线，您甚至不需要传递正在构建的字符串。

public String preOrderStringBuild(Node root) {
    if (root == null) {
        return "";
    }

    String preOrderString = root.key + " " 
        + preOrderStringBuild(root.left) 
        + preOrderStringBuild(root.right);

    return preOrderString;
}