题解 | #二叉树遍历#

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

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

/**
 * 中序遍历
 * @param root
 */
void InOrder(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    InOrder(root->leftChild);
    printf("%c ", root->data);
    InOrder(root->rightChild);
}

/**
 * 递归建树
 * @param i 当前扫描到字符串的位置
 * @param inOrder 前序遍历的字符串
 * @return 树的根结点
 */
TreeNode* RecursiveBuildTree(int& i, string inOrder) {
    char c = inOrder[i];
    i++; //i往后移
    if (c == '#') { //空结点则返回空
        return NULL;
    }
    TreeNode* treeNode = new TreeNode; //在堆中创建
    treeNode->data = c;
    treeNode->leftChild = RecursiveBuildTree(i,
                          inOrder); //这里的i是会动态变化的
    treeNode->rightChild = RecursiveBuildTree(i, inOrder);
    return treeNode;
}

int main() {
    char input[200];
    //string str = "abc##de#g##f###";
    while (scanf("%s", input) != EOF) {
        TreeNode* root;
        string inOrder = input;
        int i = 0;
        root = RecursiveBuildTree(i, inOrder);
        InOrder(root);
    }
}