题解 | #二叉树遍历#

//注意，idx设置为& ； 并且在为空树的时候依然idx++ .
#include <iostream>
using namespace std;
struct TreeNode
{
    char elem ;
    TreeNode* left ;
    TreeNode* right ; 
    TreeNode(char c):elem(c) , left(nullptr) , right(nullptr) {};
} ;
// int idx = 0 ;  // 因为树的遍历有回溯所以idx 要设为全局。 
TreeNode* build(const string & s , int &idx  ) 
{
    if(idx == s.size())
    {
        return nullptr; 
    }
    if(s[idx] == '#')
    {
        idx++ ; // 遇到为'#' 的表示为遇到无左右子树的。

        return nullptr; 
    }

    TreeNode * root = new TreeNode(s[idx] ); 
    //  
    idx++ ; 
    root->left = build(s  , idx) ;  // 左孩子
    // idx ++ ; 
    root->right = build(s , idx ) ;  // 右孩子
    return root ; 
} ; 
void inorder(TreeNode * cur)
{
    if(cur == nullptr)
    {
        return ; 
    }
    inorder(cur->left) ; 
    cout<<cur->elem<<" " ; 
    inorder(cur->right) ;
}
int main() {
// TreeNode t  ; 
string s ; 
// while(cin>>s)
// {
cin>>s ; 
int idx = 0 ; 
TreeNode* root = build(s , idx) ;
inorder(root) ;
cout<<endl ; 
// }

}
// // 64 位输出请用 printf("%lld")

// #include<iostream>
// using namespace std;
// string s ; 
// int pos;
// struct Tnode{
//     char val;
//     Tnode* left;
//     Tnode* right;
//     Tnode(char c): val(c), left(NULL), right(NULL){}
// };
// //递归建树
// Tnode* createTree(){
//     char c = s[pos++];
//     if(c == '#')//为空，返回上个节点
//         return NULL;
//     Tnode* root = new Tnode(c);//新建节点
//     root->left = createTree();//建立左子树
//     root->right = createTree();//建立右子树
//     return root;
// }
// void inOrder(Tnode* T){
//     if(!T) return ;
//     inOrder(T->left);
//     cout << T->val << " ";
//     inOrder(T->right);
// }
// int main(){
//     while(cin>>s){
//         pos = 0;
//         Tnode* root = createTree();
//         inOrder(root);
//         cout << endl;
//     }
//     return 0;
// }