题解 | #二叉树遍历#

#include <iostream>
#include <cstdio>
#include <queue>

using namespace std;

typedef char ElementType;

/*
 * 二叉树
 */
struct TreeNode {
    ElementType data;
    TreeNode* leftChild;
    TreeNode* rightChild;

    TreeNode(char c) {
        this->data = c;
        this->leftChild = nullptr;
        this->rightChild = nullptr;
    }
};

/**
 * 访问结点
 * @param node
 */
void visit(TreeNode* node);

/**
 * 后序遍历
 * @param root
 */
void postOrder(TreeNode* root);

/**
 * 由先序遍历和中序遍历构建二叉树
 * @param preOrder
 * @param inOrder
 * @return
 */
TreeNode* build(string preOrder, string inOrder) {
    if (preOrder.size() == 0) {
        return nullptr;
    }
    /*
     * 前序遍历的第一个元素必为根
     */
    char cur = preOrder[0];
    TreeNode* root = new TreeNode(cur);
    int pos = inOrder.find(cur);
    /*
     * 分别递归构建左子树和右子树
     * 对于中序遍历而言，假设中序遍历中根节点的索引为index
     * 1. 左子树元素的索引区间是[0, index-1]
     * 2. 右子树元素的索引区间是[index+1, inOrder.size()-1]
     *
     * 对于前序遍历来说，假设中序遍历中根节点的索引为index
     * 1. 左子树元素的索引区间是[1, index-1]
     * 2. 右子树元素的索引区间是[index+1, preOrder.size()-1]
     */
    root->leftChild = build(preOrder.substr(1, pos), inOrder.substr(0, pos));
    root->rightChild = build(preOrder.substr(pos + 1), inOrder.substr(pos + 1));
    return root;
}


/**
 * 遍历--清华大学
 * @return
 */
int main() {
    string preOrder;
    string inOrder;
    while (cin >> preOrder >> inOrder) {
        TreeNode* root = build(preOrder, inOrder);
        postOrder(root);
        cout << endl;
    }

    return 0;
}

void postOrder(TreeNode* root) {
    if (root == nullptr) {
        return;
    }
    /*
     * 先后遍历左子树、右子树、根
     */
    postOrder(root->leftChild);
    postOrder(root->rightChild);
    visit(root);
}

void visit(TreeNode* node) {
    cout << node->data;
}