В порядке обхода дерева

Question

Учитывая программу обхода бинарного дерева, как бы я изменил приведенную ниже функцию обхода, чтобы std :: string был возвращаемым типом, и напечатал имя каждого узла в той же строке?

void traverse(Node* head){
    if(head == nullptr) {
        return;
    }
    traverse(head->left);       //Visit left subtree
    std::cout << head->name;
    traverse(head->right);      // Visit right subtree   
}

Answer 1

Вы можете написать что-то вроде этого:

std::string traverse(Node* head){
    if(head == nullptr) {
        return "";
    }
    std::string s = traverse(head->left);       // Visit left subtree
    s += head->name + " ";
    s += traverse(head->right);                 // Visit right subtree
    return s;
}

, но если ваше дерево - бамбук:

       a  <- root
      / \
nullptr  b
        / \
 nullptr  ...
            \
             z
            / \
     nullptr   nullptr

сложность кода выше будет O(n^2), потому что правильное поддерево строка всегда копируется, и нет простых и изящных способов избежать этого.

Так что лучше не возвращать строку, а передавать ссылку на строку:

void traverse(Node* head, std::string& s){
    if(head == nullptr) {
        return;
    }
    traverse(head->left, s);       // Visit left subtree
    s += head->name + " ";
    traverse(head->right, s);      // Visit right subtree
}