Задача. Бинарное булево дерево

Дан корень полного бинарного дерева со следующими свойствами:

Конечные узлы имеют значение 0 или 1, где 0 обозначает False, а 1 - True.
Неконечные узлы имеют значение 2 или 3, где 2 обозначает логическое ИЛИ, а 3 - логическое И.

Вычисление узла происходит следующим образом:

Если узел является конечным, то берется значение узла: True или False.
В противном случае вычисляется два дочерних узла и применяется булева операция над его значением дочерних узлов.

Справка. Полное бинарное дерево - это бинарное дерево, в котором каждый узел имеет либо 0, либо 2 дочерних узла.

Необходимо вычислить результат для всего дерева.

Пример

Output: true

Разбор

Моделируем вычисление результата, для удобства функцию реализуем рекурсивно.

Так как по условию входное дерево является полным, то рекурсия остановется на конечных узлах, у которых нет обоих дочерних узлов.
Если узел конечный, т.е. у него нет дочерних узлов, возвращаем true если значение узла равно 1, в противном случае false.
Если значение узла равно 2, то нам нужно вычислить значения в дочерних узлах и вернуть результат логического ИЛИ.
В противном случае, вычисляем результат в дочерних узлах и возвращаем результат логического И.

Реализация

static bool EvaluateTree(TreeNode root) 
{
    if (root.left == null && root.right == null) {
        return root.val == 1;
    }

    bool left = EvaluateTree(root.left);
    bool right = EvaluateTree(root.right);

    return root.val == 2 ? left | right : left & right;
}

https://gist.github.com/unilecs/a81c8aeda472b7dabd4b323aee92d776

Play-test

https://dotnetfiddle.net/aXtN2l