题解 | #二叉树遍历#

思路

用完整的前序遍历重建二叉树

AC代码

#include<iostream>
using namespace std;

string s;
int idx=0;

struct TreeNode{
    char val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(char x): val(x),left(NULL),right(NULL){};
};

TreeNode* CreateTree(){
    char n=s[idx++];
    if(n=='#')  return NULL;
    auto root = new TreeNode(n);
    root->left=CreateTree();
    root->right=CreateTree();
    return root;
}

void inorder(TreeNode* root){
    if(!root) return;
    inorder(root->left);
    cout << root->val << " ";
    inorder(root->right);
}

int main(){
    cin >> s;
    auto root = CreateTree();
    inorder(root);
    return 0;
}