题解 | #二叉树遍历#

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

struct TreeNode {
    char val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(char c) : val(c), left(nullptr), right(nullptr) {}
};
//index参数类型是引用，index需要随着递归次数不断发生变化
TreeNode* creatBinaryTree(string str, int& index) {  //也可以将index设为全局变量
    char c = str[index++];
    if (c == '#' || index >= str.size()) {
        return NULL;
    }
    TreeNode* root = new TreeNode(c);
    root->left = creatBinaryTree(str, index);
    root->right = creatBinaryTree(str, index);
    return root;
}

void InOrder(TreeNode* root) {
    if (root == NULL) return;
    InOrder(root->left);
    cout << root->val << " ";
    InOrder(root->right);
}

int main() 
{
    string str;
    int index = 0;
    while (getline(cin, str)) {
        TreeNode* root = creatBinaryTree(str, index);
        InOrder(root);
        cout << endl;
    }
    return 0;
}