Sponsored
Sponsored
This approach uses recursion to evaluate the binary boolean tree. Starting from the root, recursively evaluate the left and right children of each node. If a node is a leaf, return its boolean value. If a node is non-leaf, apply the boolean operation defined by its value on its children's evaluations (OR for 2, AND for 3).
Time Complexity: O(n) where n is the number of nodes, since we need to visit each node once.
Space Complexity: O(h) where h is the height of the tree, due to the recursion stack.
1class TreeNode:
2 def __init__(self, val=0, left=None, right=None):
3 self.val = val
4 self.left = left
5 self.right = right
6
7class Solution:
8 def evaluateTree(self, root: TreeNode) -> bool:
9 if not root.left and not root.right:
10 return root.val == 1
11 left = self.evaluateTree(root.left)
12 right = self.evaluateTree(root.right)
13 return (left or right) if root.val == 2 else (left and right)Python version follows the recursive evaluation pattern where recursive calls are used for children evaluations and logical operations are applied based on the current node's value.
This method employs an iterative approach using a stack to emulate the recursive behavior. By performing a depth-first traversal, it uses a stack to track nodes and their processed children, evaluating each in line with the tree's logic operations.
Time Complexity: O(n), as all nodes are processed.
Space Complexity: O(n), given the stack memory employment.
1
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) {
if (root == null) return false;
Stack<TreeNode> stack = new Stack<TreeNode>();
stack.Push(root);
while (stack.Count > 0) {
TreeNode node = stack.Pop();
if (node.left == null && node.right == null) {
node.val = node.val == 1 ? 1 : 0;
continue;
}
if (node.left != null) stack.Push(node.left);
if (node.right != null) stack.Push(node.right);
int leftVal = node.left != null ? node.left.val : 0;
int rightVal = node.right != null ? node.right.val : 0;
if (node.val == 2) { // OR
node.val = (leftVal == 1 || rightVal == 1) ? 1 : 0;
} else if (node.val == 3) { // AND
node.val = (leftVal == 1 && rightVal == 1) ? 1 : 0;
}
}
return root.val == 1;
}
}C# employs a procedural stack to navigate node evaluations, storing temporary results atop the stack, and computing parent's value once children have been processed through logical operations.