Geek asks and answers

Balanced Sums in a Binary Tree

I found an interesting algorithmic problem. We are given a binary tree that has a value of 0 at each vertex except the leaves. In the leaves, we have two options:

  • the value is unknown, but we know that it is a positive integer> = 1

  • known, and this natural number> = 1

The task is to decide whether it is possible to set any unknown value in the leaves, so that each subtree of a given tree has the same sum of values ​​at the vertices in the left and right subtree.

For instance:

Tree1:

      0
     / \
    0   ?
   / \
  0   5
 / \
?   ?

Answer NO - given that each question mark must be a natural number, this, of course, is impossible

Tree2:

        0
     /     \
    0      0
   / \    / \
  0   10 ?   ?
 / \
5   ?

Answer: YES - we set: 5, 10, 10, respectively, in each question mark.

- , . , , . - ? .

+5
2

, . node . :

  • L R : node , L == R
  • L, R: node L R
  • L R : node , . .

, , node, . , node, 4 , 1 , 4, node 8.

. , , , .

Go, :

package main

import (
  "fmt"
)

// Assume that (Left == nil) == (Right == nil)
type Tree struct {
  Val         int
  Left, Right *Tree
}

func (t *Tree) GetWeight() (weight int, valid bool) {
  if t.Left == nil {
    return t.Val, true
  }
  l, lv := t.Left.GetWeight()
  r, rv := t.Right.GetWeight()
  if !lv || !rv {
    return 0, false
  }
  if l < 0 && r < 0 {
    if l < r {
      return 2 * l, true
    }
    return 2 * r, true
  }
  if l < 0 {
    return 2 * r, r%(-l) == 0
  }
  if r < 0 {
    return 2 * l, l%(-r) == 0
  }
  return r + l, r == l
}

func main() {
  t := Tree{0,
    &Tree{0,
      &Tree{0,
        &Tree{Val: 5},
        &Tree{Val: -1},
      },
      &Tree{Val: 10},
    },
    &Tree{0,
      &Tree{Val: -1},
      &Tree{Val: -1},
    },
  }
  w, v := t.GetWeight()
  fmt.Printf("%d, %t\n", w, v)
  t = Tree{0,
    &Tree{0,
      &Tree{0,
        &Tree{Val: -1},
        &Tree{Val: -1},
      },
      &Tree{Val: 5},
    },
    &Tree{Val: -1},
  }
  w, v = t.GetWeight()
  fmt.Printf("%d, %t\n", w, v)
}
+2

. , ( ) . , .

.

+2

More articles:


All Articles