题解 | #二叉树遍历#

#include<iostream>
#include<string>
using namespace std;
struct tree {
    char c;
    tree* lc;
    tree* rc;
    tree(char ch) {
        c = ch;
        lc = NULL;
        rc = NULL;
    }
};
string s;
int n, i;//n是s的长度，i是指向字符串的当前位置
tree* buildTree() {
    tree* root = new tree(s[i]); //类似于先序遍历，所以处理放在递归前
    if (i + 1 >= n)//可以理解成就是保护数组不越界 越界的肯定没东西啦
        return NULL;
    if (s[++i] != '#')
        root->lc = buildTree();//根左右 所以先递归左边
    if (i + 1 >= n)
        return NULL;
    if (s[++i] != '#')
        root->rc = buildTree();
    return root;
}
void inOrder(tree* t) {
    if (t == NULL)
        return;
    inOrder(t->lc);
    cout << t->c << ' ';
    inOrder(t->rc);
}
int main() {
    cin >> s;
    n = s.size();
    i = 0;
    tree* root = buildTree();
    inOrder(root);
}
// 64 位输出请用 printf("%lld")