后序遍历 Java

Question

我试图在 post 顺序遍历后 return 我的树的字符串表示，但它给了我工作。似乎是一个足够简单的代码，但我似乎无法理解。调试也没有多大帮助。我忘记了我应该看的是什么。这里出了什么问题？我知道在这个意义上使用字符串是不好的做法，但我只是把一些东西放在一起。我本可以使用字符串缓冲区或其他东西，但现在我很困惑为什么这不起作用并且想找出原因。

  public String postOrderTraversal(){
        String answer = "";
        return postOrderTraversal(root, answer);
    }

    private String postOrderTraversal(Node aux, String answer){
        if(aux == null){
            return "";
        }
        else{
            postOrderTraversal(aux.left, answer);
            postOrderTraversal(aux.right, answer);
            answer += aux.data;
        }

        return answer;

    }

Answer 1

您没有添加子树的 post 顺序遍历。您可以将其更正为

private String postOrderTraversal(Node aux) {
    if(aux == null) return "";
    return postOrderTraversal(aux.left) + postOrderTraversal(aux.right) + aux.data;
}

Answer 2

字符串是不可变对象。仅传递引用不会更新 return 值。你应该试试 StringBuilder。

public String postOrderTraversal(){
    StringBuilder answer  = new StringBuilder();
    postOrderTraversal(root, answer);
    return answer.toString();
}

private void postOrderTraversal(Node aux, StringBuilder answer){
    if(aux == null){
        return;
    }
    else{
        postOrderTraversal(aux.left, answer);
        postOrderTraversal(aux.right, answer);
        answer.append(aux.data);
    }
}

后序遍历 Java

PostOrder Traversal Java

java

recursion

binary-search-tree