牛客网计算机考研复试-KY11-二叉树的遍历

题目链接：点这里

---

题目描述：
编一个程序，读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树（以指针方式存储）。 例如如下的先序遍历字符串： ABC##DE#G##F### 其中“#”表示的是空格，空格字符代表空树。建立起此二叉树以后，再对二叉树进行中序遍历，输出遍历结果。

---

思路1：

根据先序遍历建立二叉树，在中序遍历输出结果。

---

代码1:

#include <bits/stdc++.h>
using namespace std;
string s;
int i;
struct TreeNode{
    char data;
    struct TreeNode *left,*right;
};

TreeNode* creat(){
    char c = s[i++];
    ///不用考虑s[i]超内存，有#控制，访问不到s[s.length()]
    if(c=='#')
        return NULL;
    TreeNode *root = new TreeNode();
    root->data = c;
    root->left = creat();
    root->right = creat();
    return root;
}

void inOrderTraversal(TreeNode* node){
    if(node==NULL)
        return;
    inOrderTraversal(node->left);
    cout << node->data << " ";
    inOrderTraversal(node->right);
}

int main(){
    while(cin >> s){
        i = 0;
        TreeNode *root = creat();
        inOrderTraversal(root);
    }
    return 0;
}

---

思路2：

评论里有一个很棒的思路：二叉树的先序遍历入栈，出栈顺序就是它的中序遍历（好像王道408数据结构有讲过）。

---

代码2:

#include <bits/stdc++.h>
using namespace std;

int main(){
    string s;
    while(cin >> s){
        stack<char> c;
        for(int i=0;i<s.length()-1;i++){
            if(s[i]=='#'){
                cout << c.top() << " ";
                c.pop();
            }
            else{
                c.push(s[i]);
            }
        }
        cout << endl;
    }
    return 0;
}