题解 | 二叉树遍历

#include<iostream>
#include<string>
using namespace std;

typedef struct TreeNode {
    char data;
    TreeNode* leftChild;
    TreeNode* rightChild;
} TreeNode;

void createTree(TreeNode* root, string preOrder, string inOrder) {
    if (preOrder.size() != 0) {
        //给根赋值
        root->leftChild = NULL;
        root->rightChild = NULL;
        root->data = preOrder[0];
        // 寻找左右子树子串
        int index;
        for (unsigned int i = 0; i < inOrder.size(); i++) {
            if (inOrder[i] == preOrder[0]) {
                index = i;  // 左子树长度为index 右子树长度为inOrder.size() - index - 1
            }
        }

        string sub_left_preOrder = preOrder.substr(1, index);
        string sub_left_inOrder = inOrder.substr(0, index);
        string sub_right_preOrder = preOrder.substr(index + 1,
                                    inOrder.size()   - index - 1);
        string sub_right_inOrder = inOrder.substr(index + 1,
                                   inOrder.size() - index - 1);

        // 递归创建左右子树
        if (sub_left_preOrder.size() != 0) {
            root->leftChild = (TreeNode*)malloc(sizeof(TreeNode));
            createTree(root->leftChild, sub_left_preOrder, sub_left_inOrder);
        }
        if (sub_right_preOrder.size() != 0) {
            root->rightChild = (TreeNode*)malloc(sizeof(TreeNode));
            createTree(root->rightChild, sub_right_preOrder, sub_right_inOrder);
        }
    }
}

void PostOrder(TreeNode* root) {
    if (root != NULL) {
        PostOrder(root->leftChild);
        PostOrder(root->rightChild);
        cout << root->data;
    }
}

int main() {
    string preOrder, inOrder;
    TreeNode* root;
    while (cin >> preOrder && cin >> inOrder) {
        root = (TreeNode*)malloc(sizeof(
                                     TreeNode));// 务必在外面建立好root不然会传递给空指针
        createTree(root, preOrder, inOrder);
        PostOrder(root);
        cout << endl;
    }
}