Блог пользователя wish_me

Interesting Tree problem...
Автор wish_me, история, 7 лет назад, По-английски

Find the maximum difference between any combination of child and parent node in a given binary tree. Here child node can be any level below parent node, but should be in the same sub tree starting from parent node

  • Проголосовать: нравится
  • -17
  • Проголосовать: не нравится

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Since your question is not very clear, I am assuming the following things: 1. The difference of nodes which you are talking about is the difference between given node's value and not their distance. 2. The input is a node and we have to figure out the maximum difference between the value of input node and any of the nodes in its subtree with input node as the root.

Solution: Use DFS and Segment Tree. First of all run a DFS to make preorder traversal array and at the same time calculate size of the subtree for every node. Then build a segment tree out of this preorder traversal array and query to find range maximum between starting parent node location and its size of subtree.

P.S : Do add the question link, if any!

→ Ответить
  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Yes its between the value of the nodes.Can you please explain your approach little more.And your second assumption is wrong we need to find the maximum difference for any pair of child and parent.I hope now you understand the question more clearly.

    → Ответить
    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      If i correctly understood the problem, if there are two edges 1->2, 2->3, node 1 have value 10, 2 — 30, 3 — 40, answer is 30. Solution: for each v store minimum of its subtree and maximum (it can be done during dfs). Then try to increase ans using abs(a[v] — mn[v]) and abs(a[v] — mx[v]). Complexity is O(n).

      → Ответить