顺序树遍历

Question

给定一个二叉树遍历程序，我如何修改下面的遍历函数以将 std::string 作为其 return 类型并在同一行上打印每个节点的名称？

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)，因为右子树字符串总是被复制，没有简单优雅的方法来避免这种情况。

所以最好不要return字符串，而是传递对字符串的引用：

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
}

顺序树遍历

In order tree traversal

c++

algorithm

tree

binary-tree

data-structures