Middle-テーマ68:106.Construct Binary Tree from Inorder and Postorder Traversal
1890 ワード
Given inorder and postorder traversal of a tree,construct the binary tree.1本の二叉木の中で序と後序が遍歴する序列を与えて、この二叉木を構築します.タイトル分析:中序遍歴の順序は左-中-右で、後序遍歴は左-右-中なので、後序遍歴の最後の要素から中序遍歴列にマッチングし、マッチングしてから再帰的にサブツリーの中序と後序シーケンスに基づいて左右のサブツリーを構築します.ソース:(language:c)
成績:20 ms,35.14%,衆数20 ms,43.24%Cmershenのつぶやき:本題のJavaエントリパラメータは(int[],int[]),Cではポインタを用い,サブ配列を効率的に切り取ることができる.したがって、ポインタは様々な欠陥を引き起こしやすく、危険であるが、時には大きな便利さを提供することもある.
struct TreeNode* buildTree(int* inorder, int inorderSize, int* postorder, int postorderSize) {
if(inorderSize == 0 && postorderSize == 0)
return NULL;
else {
int middle = postorder[postorderSize-1];
int i;
for (i = 0;inorder[i] != middle; i++);
struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode)); //generate root
root->val = middle;
root->left = buildTree(inorder, i, postorder, i);
root->right = buildTree(&inorder[i+1], inorderSize-i-1, &postorder[i], inorderSize-i-1);
return root;
}
}
成績:20 ms,35.14%,衆数20 ms,43.24%Cmershenのつぶやき:本題のJavaエントリパラメータは(int[],int[]),Cではポインタを用い,サブ配列を効率的に切り取ることができる.したがって、ポインタは様々な欠陥を引き起こしやすく、危険であるが、時には大きな便利さを提供することもある.