題目鏈接：

二叉樹(shù)遍歷_?？皖}霸_牛客網(wǎng)編一個(gè)程序，讀入用戶輸入的一串先序遍歷字符串，根據(jù)此字符串建立一個(gè)二叉樹(shù)（以指針?lè)绞酱鎯?chǔ)）。題目來(lái)自【?？皖}霸】https://www.nowcoder.com/share/jump/437195121692547007478

描述

編一個(gè)程序，讀入用戶輸入的一串先序遍歷字符串，根據(jù)此字符串建立一個(gè)二叉樹(shù)（以指針?lè)绞酱鎯?chǔ)）。 例如如下的先序遍歷字符串： ABC##DE#G##F### 其中“#”表示的是空格，空格字符代表空樹(shù)。建立起此二叉樹(shù)以后，再對(duì)二叉樹(shù)進(jìn)行中序遍歷，輸出遍歷結(jié)果。

輸入描述：

輸入包括1行字符串，長(zhǎng)度不超過(guò)100。

輸出描述：

可能有多組測(cè)試數(shù)據(jù)，對(duì)于每組數(shù)據(jù)， 輸出將輸入字符串建立二叉樹(shù)后中序遍歷的序列，每個(gè)字符后面都有一個(gè)空格。 每個(gè)輸出結(jié)果占一行。

示例1

輸入：

abc##de#g##f###

輸出：

c b e g d f a 

源代碼：

#include<iostream>
#include<string>
using namespace std;//例題10.1 二叉樹(shù)遍歷
struct TreeNode {char data;TreeNode* leftChild;TreeNode* rightChild;TreeNode(char c): data(c), leftChild(NULL), rightChild(NULL){}
};TreeNode* Build(int& pos, string str) {char c = str[pos++];if (c == '#') {return NULL;}TreeNode* root = new TreeNode(c);root->leftChild = Build(pos, str);root->rightChild = Build(pos, str);return root;
}void Inorder(TreeNode* root) {if (root == NULL) {return;}Inorder(root->leftChild);cout << root->data << " ";Inorder(root->rightChild);return;
}int main()
{string s;cin >> s;int pos = 0;TreeNode* root = Build(pos, s);Inorder(root);cout << endl;return 0;
}

提交結(jié)果：

?