Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/2331.html
2331. Evaluate Boolean Binary Tree
- Difficulty: Easy.
- Related Topics: Binary Search, Tree, Depth-First Search.
- Similar Questions: Check If Two Expression Trees are Equivalent, Design an Expression Tree With Evaluate Function, Minimum Flips in Binary Tree to Get Result.
Problem
You are given the root
of a full binary tree with the following properties:
-
Leaf nodes have either the value
0
or1
, where0
representsFalse
and1
representsTrue
. -
Non-leaf nodes have either the value
2
or3
, where2
represents the booleanOR
and3
represents the booleanAND
.
The evaluation of a node is as follows:
-
If the node is a leaf node, the evaluation is the value of the node, i.e.
True
orFalse
. -
Otherwise, evaluate the node’s two children and apply the boolean operation of its value with the children’s evaluations.
Return** the boolean result of evaluating the root
node.**
A full binary tree is a binary tree where each node has either 0
or 2
children.
A leaf node is a node that has zero children.
Example 1:
Input: root = [2,1,3,null,null,0,1]
Output: true
Explanation: The above diagram illustrates the evaluation process.
The AND node evaluates to False AND True = False.
The OR node evaluates to True OR False = True.
The root node evaluates to True, so we return true.
Example 2:
Input: root = [0]
Output: false
Explanation: The root node is a leaf node and it evaluates to false, so we return false.
Constraints:
-
The number of nodes in the tree is in the range
[1, 1000]
. -
0 <= Node.val <= 3
-
Every node has either
0
or2
children. -
Leaf nodes have a value of
0
or1
. -
Non-leaf nodes have a value of
2
or3
.
Solution (Java, C++, Python)
-
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public boolean evaluateTree(TreeNode root) { if (root.left == null) { return root.val == 1; } else { if (root.val == 2) { return evaluateTree(root.left) || evaluateTree(root.right); } else { return evaluateTree(root.left) && evaluateTree(root.right); } } } } ############ /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public boolean evaluateTree(TreeNode root) { if (root.left == null) { return root.val == 1; } boolean l = evaluateTree(root.left); boolean r = evaluateTree(root.right); return root.val == 2 ? l || r : l && r; } }
-
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def evaluateTree(self, root: Optional[TreeNode]) -> bool: if root.left is None: return bool(root.val) l = self.evaluateTree(root.left) r = self.evaluateTree(root.right) return l or r if root.val == 2 else l and r ############ # 2331. Evaluate Boolean Binary Tree # https://leetcode.com/problems/evaluate-boolean-binary-tree/ # Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def evaluateTree(self, root: Optional[TreeNode]) -> bool: def go(node): if not node.left and not node.right: return node.val == 1 left, right = go(node.left), go(node.right) return left or right if node.val == 2 else left and right return go(root)
-
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: bool evaluateTree(TreeNode* root) { if (!root->left) { return root->val; } bool l = evaluateTree(root->left); bool r = evaluateTree(root->right); return root->val == 2 ? l or r : l and r; } };
-
/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ func evaluateTree(root *TreeNode) bool { if root.Left == nil { return root.Val == 1 } l, r := evaluateTree(root.Left), evaluateTree(root.Right) if root.Val == 2 { return l || r } return l && r }
-
/** * Definition for a binary tree node. * class TreeNode { * val: number * left: TreeNode | null * right: TreeNode | null * constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } * } */ function evaluateTree(root: TreeNode | null): boolean { const { val, left, right } = root; if (left == null) { return val === 1; } if (val === 2) { return evaluateTree(left) || evaluateTree(right); } return evaluateTree(left) && evaluateTree(right); }
-
// Definition for a binary tree node. // #[derive(Debug, PartialEq, Eq)] // pub struct TreeNode { // pub val: i32, // pub left: Option<Rc<RefCell<TreeNode>>>, // pub right: Option<Rc<RefCell<TreeNode>>>, // } // // impl TreeNode { // #[inline] // pub fn new(val: i32) -> Self { // TreeNode { // val, // left: None, // right: None // } // } // } use std::rc::Rc; use std::cell::RefCell; impl Solution { fn dfs(root: &Option<Rc<RefCell<TreeNode>>>) -> bool { let root = root.as_ref().unwrap().as_ref().borrow(); if root.left.is_none() { return root.val == 1; } if root.val == 2 { return Self::dfs(&root.left) || Self::dfs(&root.right); } Self::dfs(&root.left) && Self::dfs(&root.right) } pub fn evaluate_tree(root: Option<Rc<RefCell<TreeNode>>>) -> bool { Self::dfs(&root) } }
Explain:
nope.
Complexity:
- Time complexity : O(n).
- Space complexity : O(n).