2331. Evaluate Boolean Binary Tree

EasyView on LeetCode

Tree Depth-First Search Binary Tree

Time: O(n)

Space: O(n)

Intuition

Evaluate boolean tree: leaves are 0/1, internal nodes are OR (2) or AND (3). Post-order DFS.

Algorithm

1DFS. If leaf: return val==1. If OR node: return left || right. If AND node: return left && right.

Common Pitfalls

•Post-order evaluation. OR=2, AND=3. Return boolean.

2331.cs

// Approach: DFS post-order; leaf returns its value; internal node applies OR/AND to children.
// Time: O(n) Space: O(n)

public class TreeNode
{
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null)
    {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class Solution
{
    public bool EvaluateTree(TreeNode root)
    {
        return EvaluateBoolean(root);
    }

    private bool EvaluateBoolean(TreeNode root)
    {
        if (root.val < 2)
            return root.val == 1 ? true : false;

        if (root.val == 2)
            return EvaluateBoolean(root.left) | EvaluateBoolean(root.right);

        return EvaluateBoolean(root.left) & EvaluateBoolean(root.right);
    }
}

Was this solution helpful?