递归建树,子树为空返回NULL
#include <iostream> using namespace std; struct treeNode { char letter; treeNode* leftChild; treeNode* rightChild; treeNode(char c) { letter = c; leftChild = NULL; rightChild = NULL; } }; treeNode* buildTree(string preOrderStr, string inOrderStr) { if (preOrderStr.size() == 0) { return NULL; } treeNode* newNode = new treeNode(preOrderStr[0]); int pos = inOrderStr.find(preOrderStr[0]); newNode->leftChild = buildTree(preOrderStr.substr(1, pos), inOrderStr.substr(0, pos)); newNode->rightChild = buildTree(preOrderStr.substr(pos + 1), inOrderStr.substr(pos + 1)); return newNode; } void postOrder(treeNode* root) { if (root == NULL) return; postOrder(root->leftChild); postOrder(root->rightChild); cout << root->letter; } int main() { string a, b; while (cin >> a >> b) { // 注意 while 处理多个 case treeNode* tree = buildTree(a, b); postOrder(tree); cout << endl; } } // 64 位输出请用 printf("%lld")