Post History
C (gcc), 114 bytes f(int n,int*p,int*i,int**o){if(n){int*m=i,k;for(;*m!=*p;++m);k=m-i;f(k,p+1,i,o);f(n-k-1,p+k+1,m+1,o);*(*o)++=*p;}} Try it online! Arguments: n is the length of the arra...
Answer
#3: Post edited
by
celtschk
·
2020-11-30T18:43:41Z (almost 4 years ago)
I forgot to replace some variable names in the ungolfed version; also improved formatting of that version slightly
- # [C (gcc)], 114 bytes
- <!-- language-all: lang-c -->
- f(int n,int*p,int*i,int**o){if(n){int*m=i,k;for(;*m!=*p;++m);k=m-i;f(k,p+1,i,o);f(n-k-1,p+k+1,m+1,o);*(*o)++=*p;}}
- [Try it online!][TIO-ki4tzr0p]
- Arguments:
- * `n` is the length of the arrays
- * `p` is the preorder array
- * `i` is the inorder array
- * `o` is a pointer to a pointer to where the postorder array is to be stored.
- Here's an ungolfed and commented version:
- ```
f(int size,int *preorder, int *inorder, int **output)- {
if(size) /* if the arrays are zero length, do nothing */- {
- /* The first element of the preorder array is the root.
- Find it in the inorder array. */
- int *m = inorder, k;
- for(;*m != *preorder; ++m);
- /* everything preceding the root in the inorder list
- is in the left subtree; store its length in k */
- k = m - inorder;
- /* recursively call the function for the left and right
- subtree */
f(k,p+1,i,o);f(n-k-1,p+k+1,m+1,o);- /* finally, append the value of the root node */
*(*o)++=*p;- }
- }
- ```
- [C (gcc)]: https://gcc.gnu.org/
- [TIO-ki4tzr0p]: https://tio.run/##ZZHLTsMwEEX3@YqhCOQkU4hLX8iEH4EsqrSmVohjJemGKt8erk0KlVh4LM8cn/GjnH@U5ThqYWxPlhETF6IJMWnis9HCImJV54YrpZtWqKS@yROn0rSOVZXXc6O0qNilkg03MRZ2Xs0lEhVSNQaSiYAuTf2@YRhvjS0/T/sDvXT93jQPx9co8oeod8aKODpHRH7p2kPT7g/tW0E5nSljkkwLpiemJdOKac20YdoyPaPky6hLABKEBCLBSEASlAQmwS0yGtTUwNhr/zKYF6HLJsi3ocskzyb3cvKvpn7byb/@7@/M1wFqPzVaXK4TP04JIPEFdU3X/xzGFwumxDlsvf/LZ4WKAGvhAf59HL7cggG74CuPu5bKxnZ9QrruoZnd7We@gv@j8N0GyUxhegmnU5SmJgbgn57gBqMF9vLVwUwR7HRxMk3WAcOd@k7M3u0MzBCN3w "C (gcc) – Try It Online"
- # [C (gcc)], 114 bytes
- <!-- language-all: lang-c -->
- f(int n,int*p,int*i,int**o){if(n){int*m=i,k;for(;*m!=*p;++m);k=m-i;f(k,p+1,i,o);f(n-k-1,p+k+1,m+1,o);*(*o)++=*p;}}
- [Try it online!][TIO-ki4tzr0p]
- Arguments:
- * `n` is the length of the arrays
- * `p` is the preorder array
- * `i` is the inorder array
- * `o` is a pointer to a pointer to where the postorder array is to be stored.
- Here's an ungolfed and commented version:
- ```
- f(int size, int *preorder, int *inorder, int **output)
- {
- if (size) /* if the arrays are zero length, do nothing */
- {
- /* The first element of the preorder array is the root.
- Find it in the inorder array. */
- int *m = inorder, k;
- for(;*m != *preorder; ++m);
- /* everything preceding the root in the inorder list
- is in the left subtree; store its length in k */
- k = m - inorder;
- /* recursively call the function for the left and right
- subtree */
- f(k, preorder + 1, i, output);
- f(size - k - 1, preorder + k + 1, m + 1, output);
- /* finally, append the value of the root node */
- *(*output)++ = *preorder;
- }
- }
- ```
- [C (gcc)]: https://gcc.gnu.org/
- [TIO-ki4tzr0p]: https://tio.run/##ZZHLTsMwEEX3@YqhCOQkU4hLX8iEH4EsqrSmVohjJemGKt8erk0KlVh4LM8cn/GjnH@U5ThqYWxPlhETF6IJMWnis9HCImJV54YrpZtWqKS@yROn0rSOVZXXc6O0qNilkg03MRZ2Xs0lEhVSNQaSiYAuTf2@YRhvjS0/T/sDvXT93jQPx9co8oeod8aKODpHRH7p2kPT7g/tW0E5nSljkkwLpiemJdOKac20YdoyPaPky6hLABKEBCLBSEASlAQmwS0yGtTUwNhr/zKYF6HLJsi3ocskzyb3cvKvpn7byb/@7@/M1wFqPzVaXK4TP04JIPEFdU3X/xzGFwumxDlsvf/LZ4WKAGvhAf59HL7cggG74CuPu5bKxnZ9QrruoZnd7We@gv@j8N0GyUxhegmnU5SmJgbgn57gBqMF9vLVwUwR7HRxMk3WAcOd@k7M3u0MzBCN3w "C (gcc) – Try It Online"
#2: Post edited
by
celtschk
·
2020-11-30T17:46:36Z (almost 4 years ago)
ungolfed/commented version
- # [C (gcc)], 114 bytes
- <!-- language-all: lang-c -->
- f(int n,int*p,int*i,int**o){if(n){int*m=i,k;for(;*m!=*p;++m);k=m-i;f(k,p+1,i,o);f(n-k-1,p+k+1,m+1,o);*(*o)++=*p;}}
- [Try it online!][TIO-ki4tzr0p]
- [C (gcc)]: https://gcc.gnu.org/
- [TIO-ki4tzr0p]: https://tio.run/##ZZHLTsMwEEX3@YqhCOQkU4hLX8iEH4EsqrSmVohjJemGKt8erk0KlVh4LM8cn/GjnH@U5ThqYWxPlhETF6IJMWnis9HCImJV54YrpZtWqKS@yROn0rSOVZXXc6O0qNilkg03MRZ2Xs0lEhVSNQaSiYAuTf2@YRhvjS0/T/sDvXT93jQPx9co8oeod8aKODpHRH7p2kPT7g/tW0E5nSljkkwLpiemJdOKac20YdoyPaPky6hLABKEBCLBSEASlAQmwS0yGtTUwNhr/zKYF6HLJsi3ocskzyb3cvKvpn7byb/@7@/M1wFqPzVaXK4TP04JIPEFdU3X/xzGFwumxDlsvf/LZ4WKAGvhAf59HL7cggG74CuPu5bKxnZ9QrruoZnd7We@gv@j8N0GyUxhegmnU5SmJgbgn57gBqMF9vLVwUwR7HRxMk3WAcOd@k7M3u0MzBCN3w "C (gcc) – Try It Online"
- # [C (gcc)], 114 bytes
- <!-- language-all: lang-c -->
- f(int n,int*p,int*i,int**o){if(n){int*m=i,k;for(;*m!=*p;++m);k=m-i;f(k,p+1,i,o);f(n-k-1,p+k+1,m+1,o);*(*o)++=*p;}}
- [Try it online!][TIO-ki4tzr0p]
- Arguments:
- * `n` is the length of the arrays
- * `p` is the preorder array
- * `i` is the inorder array
- * `o` is a pointer to a pointer to where the postorder array is to be stored.
- Here's an ungolfed and commented version:
- ```
- f(int size,int *preorder, int *inorder, int **output)
- {
- if(size) /* if the arrays are zero length, do nothing */
- {
- /* The first element of the preorder array is the root.
- Find it in the inorder array. */
- int *m = inorder, k;
- for(;*m != *preorder; ++m);
- /* everything preceding the root in the inorder list
- is in the left subtree; store its length in k */
- k = m - inorder;
- /* recursively call the function for the left and right
- subtree */
- f(k,p+1,i,o);
- f(n-k-1,p+k+1,m+1,o);
- /* finally, append the value of the root node */
- *(*o)++=*p;
- }
- }
- ```
- [C (gcc)]: https://gcc.gnu.org/
- [TIO-ki4tzr0p]: https://tio.run/##ZZHLTsMwEEX3@YqhCOQkU4hLX8iEH4EsqrSmVohjJemGKt8erk0KlVh4LM8cn/GjnH@U5ThqYWxPlhETF6IJMWnis9HCImJV54YrpZtWqKS@yROn0rSOVZXXc6O0qNilkg03MRZ2Xs0lEhVSNQaSiYAuTf2@YRhvjS0/T/sDvXT93jQPx9co8oeod8aKODpHRH7p2kPT7g/tW0E5nSljkkwLpiemJdOKac20YdoyPaPky6hLABKEBCLBSEASlAQmwS0yGtTUwNhr/zKYF6HLJsi3ocskzyb3cvKvpn7byb/@7@/M1wFqPzVaXK4TP04JIPEFdU3X/xzGFwumxDlsvf/LZ4WKAGvhAf59HL7cggG74CuPu5bKxnZ9QrruoZnd7We@gv@j8N0GyUxhegmnU5SmJgbgn57gBqMF9vLVwUwR7HRxMk3WAcOd@k7M3u0MzBCN3w "C (gcc) – Try It Online"
#1: Initial revision
by
celtschk
·
2020-11-30T17:34:30Z (almost 4 years ago)
# [C (gcc)], 114 bytes
<!-- language-all: lang-c -->
f(int n,int*p,int*i,int**o){if(n){int*m=i,k;for(;*m!=*p;++m);k=m-i;f(k,p+1,i,o);f(n-k-1,p+k+1,m+1,o);*(*o)++=*p;}}
[Try it online!][TIO-ki4tzr0p]
[C (gcc)]: https://gcc.gnu.org/
[TIO-ki4tzr0p]: https://tio.run/##ZZHLTsMwEEX3@YqhCOQkU4hLX8iEH4EsqrSmVohjJemGKt8erk0KlVh4LM8cn/GjnH@U5ThqYWxPlhETF6IJMWnis9HCImJV54YrpZtWqKS@yROn0rSOVZXXc6O0qNilkg03MRZ2Xs0lEhVSNQaSiYAuTf2@YRhvjS0/T/sDvXT93jQPx9co8oeod8aKODpHRH7p2kPT7g/tW0E5nSljkkwLpiemJdOKac20YdoyPaPky6hLABKEBCLBSEASlAQmwS0yGtTUwNhr/zKYF6HLJsi3ocskzyb3cvKvpn7byb/@7@/M1wFqPzVaXK4TP04JIPEFdU3X/xzGFwumxDlsvf/LZ4WKAGvhAf59HL7cggG74CuPu5bKxnZ9QrruoZnd7We@gv@j8N0GyUxhegmnU5SmJgbgn57gBqMF9vLVwUwR7HRxMk3WAcOd@k7M3u0MzBCN3w "C (gcc) – Try It Online"