В этом посте мы собираемся обсудить leetcode 1145 — Binary Tree Coloring Game, который задают в интервью Google.

Анализ проблемы

Два игрока играют в пошаговую игру на бинарном дереве. Нам дан root этого бинарного дерева и количество узлов n в дереве. n нечетно, и каждый узел имеет свое значение от 1 до n.

Первоначально первый игрок называет значение x с помощью 1 <= x <= n, а второй игрок называет значение y с помощью 1 <= y <= n и y != x. Первый игрок раскрашивает узел значением x…