Given any two nodes in a binary tree, find the path from 1st node to another, and tell if the path is a straight line, or there are turns on the line, find number of turns.
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3690 |
| 2 | jiangly | 3647 |
| 3 | Benq | 3581 |
| 4 | orzdevinwang | 3570 |
| 5 | Geothermal | 3569 |
| 5 | cnnfls_csy | 3569 |
| 7 | Radewoosh | 3509 |
| 8 | ecnerwala | 3486 |
| 9 | jqdai0815 | 3474 |
| 10 | gyh20 | 3447 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | awoo | 164 |
| 3 | adamant | 163 |
| 4 | TheScrasse | 159 |
| 5 | nor | 157 |
| 6 | maroonrk | 155 |
| 7 | -is-this-fft- | 152 |
| 8 | Petr | 146 |
| 8 | orz | 146 |
| 10 | BledDest | 145 |
u just do binary lifting, and find lca first
(u->v) = (u->lca) + (v->lca)
then u precomp d[i][j] which represenst how many turns there are when u walk 2j steps upwards
Can you explain little more?
Maybe you should read about jump pointers.
If you represent your node(it's index) by binary number, number of turns is number of adjacent pairs of different digits in that number. So, you can easily calculate number of 'turns' from root to both of them, and you could calculate that for U, V, and LCA. Then you can combine them to get a solution.