wish_me's blog

Problem On tree.
By wish_me, history, 7 years ago, In English

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.

  • Vote: I like it
  • -5
  • Vote: I do not like it

Comments Comments (4)
| Write comment?
»
7 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it
Spoiler
→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply