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)
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ではポインタを用い,サブ配列を効率的に切り取ることができる.したがって、ポインタは様々な欠陥を引き起こしやすく、危険であるが、時には大きな便利さを提供することもある.