Swap the left and right of each node in a binary tree

Binary linked list is used as the storage structure of binary tree , Swap the left child and right child of each node in the binary tree .

Input format :

Enter the sequence of the binary tree .

Tips ： The preorder of a binary tree is a string , If the character is ‘#’, Indicates that the binary tree is empty , Otherwise, the character is the data element of the corresponding node .

Output format :

There are two lines of output ：

The first line is the middle order traversal sequence of the original binary tree ;

The second line is the middle order traversal sequence of the binary tree after exchange .

sample input :

ABC##DE#G##F###

sample output :

CBEGDFA

AFDGEBC

#include "bits/stdc++.h"

using namespace std;

struct Tree{
    char val;
    Tree* lchild;
    Tree* rchild;
};
int len = 0;
Tree* bulid(){
    char c;
    cin >> c;
    if(c=='#') return NULL;
    Tree* root = new Tree();
    root->val = c;
    root->lchild = bulid();
    root->rchild = bulid();
    return root;
}
string s;
void dfs(Tree* root){
    if(root == NULL) return;
    if(root->lchild) dfs(root->lchild);
    s+=root->val;
    if(root->rchild) dfs(root->rchild);
}
int main()
{
    Tree* root = bulid();
    dfs(root);
    cout << s<< endl;
    reverse(s.begin(),s.end());
    cout << s<< endl;
    return 0;
}