题解 | #二叉树遍历#

#include <iostream>
#include <string>
using namespace std;

struct TreeNode {
    char val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(char v) : val(v), left(nullptr), right(nullptr) {}
};

TreeNode* preOrder(string& pre, int& i) {
    char ch = pre[i++];
    if (ch == '#') 
        return nullptr;
    
    TreeNode* root = new TreeNode(ch);
    root->left = preOrder(pre, i);
    root->right = preOrder(pre, i);

    return root;
}

void InOrder(TreeNode* root)
{
    if (root == nullptr)
        return;

    InOrder(root->left);
    cout <<root->val << " ";
    InOrder(root->right);
}

int main() 
{
    string pre;
    cin >> pre;

    int i = 0;
    TreeNode* root = preOrder(pre, i);

    InOrder(root);
    cout << endl;
    return 0;
}

利用前序递归重建树最关键的部分，要记得i++。包括pos[i]='#'的时候。

TreeNode* preOrder(string& pre, int& i) {
    char ch = pre[i++];
    if (ch == '#') 
        return nullptr;
    
    TreeNode* root = new TreeNode(ch);
    root->left = preOrder(pre, i);
    root->right = preOrder(pre, i);

    return root;
}

TreeNode* preOrder(string& pre, int& i) {
    if (pre[i] == '#') {
        i++;
        return nullptr;
    }
    
    TreeNode* root = new TreeNode(pre[i++]);
    root->left = preOrder(pre, i);
    root->right = preOrder(pre, i);

    return root;
}