题解 | #二叉树遍历#

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
typedef struct Tnode {
  char data;
  struct Tnode* lchild;
  struct Tnode* rchild;
} Tnode;
void maketree(int pos, Tnode* root, char* pre, char* mid) { //构造树

  if (pre[pos] != '\0') {
    char lpre[27] = {'\0'};
    char rpre[27] = {'\0'};
    char lmid[27] = {'\0'};
    char rmid[27] = {'\0'};
    //  printf("%c",rpre[0]);
    Tnode* r, *l;
    int midpos;
    root->data = pre[pos];
    for (int i = 0; i < 27; i++) {
      if (mid[i] == pre[pos]) {
        midpos = i;
        break;
      }
    }
    if (pre[pos + 1] != '\0') {
      l = (Tnode*)calloc(1, sizeof(Tnode));
      root->lchild = l;
    }
    if (pre[pos + midpos + 1] != '\0') {
      r = (Tnode*)calloc(1, sizeof(Tnode));
      root->rchild = r;
    }
    for (int i = 0; i < midpos; i++) {
      lpre[i] = pre[pos + 1 + i];
      lmid[i] = mid[i];
    }
    int i = 0;
    while (pre[midpos + 1 + i] != '\0') {
      rpre[i] = pre[midpos + 1 + i];
      rmid[i] = mid[midpos + 1 + i];
      i++;
    }
    maketree(pos, l, lpre, lmid); //构造左子树
    maketree(pos, r, rpre, rmid); //构造右子树

  } else {
    return ;
  }
}
void lastorder(Tnode* root) {
  if (root != NULL) {
    lastorder(root->lchild);
    lastorder(root->rchild);
    if (root->data != '\0') {
      printf("%c", root->data);
    }
  } else {
    return ;
  }
}
int  main() {
  char pre[27];
  char mid[27];
  while (scanf("%s\n%s", &pre, &mid) != EOF) {
    Tnode* root = (Tnode*)calloc(1, sizeof(Tnode));
    maketree(0, root, pre, mid);
    lastorder(root);
    printf("\n");
  }

}