Leetcode 2331: Evaluate Boolean Binary Tree
You are given the root of a full binary tree. The leaf nodes hold boolean values: 0 (False) and 1 (True). The non-leaf nodes hold values 2 (OR) or 3 (AND). Your task is to evaluate the tree according to the logical operations and return the final boolean result of the root node.
Problem
Approach
Steps
Complexity
Input: You are given the root of a full binary tree. Each node has a value of 0 or 1 (leaf nodes), or 2 (OR) or 3 (AND) for non-leaf nodes.
Example: root = [3, 2, 1, null, null, 0, 1]
Constraints:
• 1 <= Number of nodes <= 1000
• Each node has either 0 or 2 children.
• Leaf nodes have value 0 or 1, non-leaf nodes have value 2 or 3.
Output: Return the boolean result of evaluating the root node of the tree.
Example: Output: true
Constraints:
• The output should be a boolean value (true or false).
Goal: Evaluate the binary tree using logical operations (AND/OR) and return the result at the root node.
Steps:
• Check if the current node is a leaf node. If so, return its value.
• If the current node is not a leaf, recursively evaluate the left and right children.
• If the node is an AND node (value 3), return the result of applying AND on the left and right children's evaluations.
• If the node is an OR node (value 2), return the result of applying OR on the left and right children's evaluations.
Goal: The constraints involve ensuring that the binary tree follows the structure of a full binary tree and that nodes hold values within the specified limits.
Steps:
• The number of nodes in the tree is in the range [1, 1000].
• Leaf nodes have a value of 0 or 1.
• Non-leaf nodes have a value of 2 or 3.
• Every node has either 0 or 2 children.
Assumptions:
• The tree is a full binary tree, meaning each non-leaf node has exactly two children.
• The leaf nodes' values are either 0 or 1, representing boolean False and True respectively.
• Non-leaf nodes' values are either 2 (for OR operation) or 3 (for AND operation).
• Input: root = [3, 2, 1, null, null, 0, 1]
• Explanation: The evaluation starts from the leaf nodes. The OR operation at the left child evaluates to 1, and the AND operation at the root results in true.
• Input: root = [2, 0, 0]
• Explanation: The OR operation at the root evaluates to false since both children are 0 (False).
Approach: We recursively evaluate the binary tree by checking each node's value. If the node is a leaf, we return its value. Otherwise, we evaluate its children and apply the corresponding logical operation.
Observations:
• Each node's value either indicates a leaf (0 or 1) or a logical operation (2 for OR, 3 for AND).
• We can use a recursive approach to evaluate each node based on whether it is a leaf or a non-leaf.
Steps:
• 1. If the node is a leaf, return its value (either 0 or 1).
• 2. If the node is non-leaf (2 or 3), recursively evaluate the left and right children.
• 3. Apply the corresponding logical operation (OR for 2, AND for 3) on the evaluations of the children.
Empty Inputs:
• No tree (null input) should be handled.
Large Inputs:
• Large trees with 1000 nodes.
Special Values:
• A single leaf node with value 1 or 0.
Constraints:
• Ensure that the tree is properly constructed with each node having either 0 or 2 children.
bool evaluateTree(TreeNode* root) {
if(!root) return false;
if(!root->left && !root->right) return root->val;
if(root->val == 2)
return evaluateTree(root->left) || evaluateTree(root->right);
else
return evaluateTree(root->left) && evaluateTree(root->right);
}
1 : Function Declaration
bool evaluateTree(TreeNode* root) {
Declares the function `evaluateTree`, which takes a `TreeNode* root` as input and returns a boolean value (`true` or `false`). It evaluates the logical expression represented by a binary tree.
2 : Base Case Check
if(!root) return false;
Checks if the current node is `null`. If the node is `null`, it returns `false` as there is no logical expression to evaluate.
3 : Leaf Node Check
if(!root->left && !root->right) return root->val;
If the node is a leaf node (no left or right child), it simply returns the value of the node (`root->val`), which is either 0 or 1.
4 : OR Operation Check
if(root->val == 2)
Checks if the current node represents an OR operation (denoted by `2`). If it does, the function will recursively evaluate the left and right children using the logical OR operation.
5 : OR Operation Evaluation
return evaluateTree(root->left) || evaluateTree(root->right);
If the current node is an OR operator, it evaluates the left and right children and returns the logical OR of their results.
6 : AND Operation Check
else
If the node is not an OR operator (i.e., it must be an AND operator, denoted by `3`), the function proceeds to the AND evaluation.
7 : AND Operation Evaluation
return evaluateTree(root->left) && evaluateTree(root->right);
If the current node is an AND operator, it evaluates the left and right children and returns the logical AND of their results.
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)
Description: The time complexity is linear, as we visit each node in the tree once.
Best Case: O(1)
Worst Case: O(n)
Description: The space complexity is O(n) due to the recursive stack in the worst case, where n is the number of nodes in the tree.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus