src/tree/btree_make_post_pi/lib.hpp
| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | #pragma once | ||
| 2 | |||
| 3 | #include "../../util/alias/others/lib.hpp" | ||
| 4 | |||
| 5 | namespace tifa_libs { | ||
| 6 | |||
| 7 | namespace btree_make_post_pi_impl_ { | ||
| 8 | 548 | CEXP void dfs(spnu pre, spnu in, vecu& post, u32& p, u32 l, u32 r) NE { | |
| 9 |
2/2✓ Branch 0 taken 284 times.
✓ Branch 1 taken 264 times.
|
548 | if (l >= r) return; |
| 10 | 264 | cu32 rt = pre[p++]; | |
| 11 | 264 | u32 m = -1_u32; | |
| 12 |
2/2✓ Branch 0 taken 2402 times.
✓ Branch 1 taken 264 times.
|
2666 | flt_ (u32, i, l, r) |
| 13 |
2/2✓ Branch 1 taken 264 times.
✓ Branch 2 taken 2138 times.
|
2402 | if (in[i] == rt) m = i; |
| 14 | 264 | dfs(pre, in, post, p, l, m), dfs(pre, in, post, p, m + 1, r), post.push_back(rt); | |
| 15 | } | ||
| 16 | } // namespace btree_make_post_pi_impl_ | ||
| 17 | |||
| 18 | 20 | CEXP vecu btree_make_post_pi(spnu pre_order, spnu in_order) NE { | |
| 19 |
1/2✗ Branch 2 not taken.
✓ Branch 3 taken 20 times.
|
20 | assert(pre_order.size() == in_order.size()); |
| 20 | 20 | vecu ret; | |
| 21 | 20 | u32 pos = 0; | |
| 22 | 20 | btree_make_post_pi_impl_::dfs(pre_order, in_order, ret, pos, 0, (u32)pre_order.size()); | |
| 23 | 20 | return ret; | |
| 24 | } | ||
| 25 | |||
| 26 | } // namespace tifa_libs | ||
| 27 |