sdut原題鏈接
求二叉樹的深度 Time Limit: 1000MS Memory Limit: 65536KB
PRoblem Description 已知一顆二叉樹的中序遍歷序列和后序遍歷序列，求二叉樹的深度。
Input 輸入數(shù)據(jù)有多組，輸入T，代表有T組數(shù)據(jù)。每組數(shù)據(jù)包括兩個長度小于50的字符串，第一個字符串表示二叉樹的中序遍歷，第二個表示二叉樹的后序遍歷。
Output 輸出二叉樹的深度。
Example Input 2 dbgeafc dgebfca lnixu linux
Example Output 4 3
Hint
Author
以下為accepted代碼
#include <stdio.h>#include <string.h>#include <stdlib.h>typedef struct node{ char date; struct node *left; struct node *right;}BinTree;BinTree *root;char st1[54], st2[54];BinTree * get_build(int len, char *st1, char *st2)//建立二叉樹函數(shù){ if(len <= 0) return NULL; BinTree *root; root = (BinTree *)malloc(sizeof(BinTree)); root->date = st2[len-1];//尋找樹節(jié)點(diǎn)，新的樹節(jié)點(diǎn)為后序遍歷st2的最后一個 int p = strchr(st1, st2[len-1]) - st1;//尋找新的樹節(jié)點(diǎn)在中序遍歷st1中的位置 root->left = get_build(p, st1, st2);//（左子樹的長度，左子樹在中序遍歷st1中的開始位置，左子樹在后序遍歷st2中的開始位置） root->right = get_build(len-p-1, st1+p+1, st2+p);//（右子樹的長度，右子樹在中序遍歷st1中的開始位置，右子樹在后序遍歷st2中的開始位置） return root;}int get_hight(BinTree *root)//計算樹的深度函數(shù){ if(root) { int HL, HR, MAXH; HL = get_hight(root->left); HR = get_hight(root->right); MAXH = HL>HR? HL: HR; return (MAXH+1); } else return 0;}int main(){ int T, len, y; scanf("%d", &T); while(T--) { scanf("%s %s", st1, st2); len = strlen(st1); root = get_build(len, st1, st2);//調(diào)用建立二叉樹函數(shù) y = get_hight(root);//調(diào)用計算二叉樹深度函數(shù) printf("%d/n", y); } return 0;}/***************************************************User name: jk160630Result: AcceptedTake time: 0msTake Memory: 108KBSubmit time: 2017-02-07 20:59:17****************************************************/新聞熱點(diǎn)
疑難解答
