二叉树：由已知两种遍历求未知遍历

2019-11-10 19:46:55

字体：大中小

来源：转载

供稿：网友

已知前序和中序遍历求后序遍历序列

struct node *creat(char *a, char *b, int n) { struct node *ptr; char *p; int count = 0; if (n <= 0) return NULL; ptr = (struct node *)malloc(sizeof(struct node)); ptr -> data = *a; for (p = &b[0]; p <= b + n - 1;p ++) { if (*p == *a) break; } count = p - b; ptr -> l = creat(a + 1, b, count); ptr -> r = creat(a + 1 + count, p + 1, n - 1 - count); return ptr; }

已知中序和后序遍历求前序遍历序列

struct node *creat(char *a, char *b, int n) { struct node *ptr; if (n <= 0) return NULL; ptr = (struct node *)malloc(sizeof(struct node)); ptr -> data = b[n - 1]; int q = strchr(a, b[n - 1]) - a; ptr -> l = creat(a, b, q); ptr -> r = creat(a + q + 1, b + q, n - q - 1); return ptr; }

上一篇：264. Ugly Number II -Medium

下一篇：POJ 3579 Median（2次二分）