A binary expression tree is a kind of binary tree used to represent arithmetic expressions. Each node of a binary expression tree has either zero or two children. Leaf nodes (nodes with 0 children) correspond to operands (variables), and internal nodes (nodes with two children) correspond to the operators. In this problem, we only consider the '+' operator (i.e. addition).
You are given the roots of two binary expression trees, root1 and root2. Return true if the two binary expression trees are equivalent. Otherwise, return false.
Two binary expression trees are equivalent if they evaluate to the same value regardless of what the variables are set to.
Example 1:
Input: root1 = [x], root2 = [x] Output: true
Example 2:
Input: root1 = [+,a,+,null,null,b,c], root2 = [+,+,a,b,c]
Output: true
Explaination: a + (b + c) == (b + c) + a
Example 3:
Input: root1 = [+,a,+,null,null,b,c], root2 = [+,+,a,b,d]
Output: false
Explaination: a + (b + c) != (b + d) + a
Constraints:
- The number of nodes in both trees are equal, odd and, in the range
[1, 4999]. Node.valis'+'or a lower-case English letter.- It's guaranteed that the tree given is a valid binary expression tree.
Follow up: What will you change in your solution if the tree also supports the '-' operator (i.e. subtraction)?
# Definition for a binary tree node.
# class Node(object):
# def __init__(self, val=" ", left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def checkEquivalence(self, root1: 'Node', root2: 'Node') -> bool:
counter = [0] * 26
def dfs(root, incr):
if root:
dfs(root.left, incr)
dfs(root.right, incr)
if root.val != '+':
counter[ord(root.val) - ord('a')] += incr
dfs(root1, 1)
dfs(root2, -1)
return counter.count(0) == 26# Definition for a binary tree node.
# class Node(object):
# def __init__(self, val=" ", left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def checkEquivalence(self, root1: 'Node', root2: 'Node') -> bool:
def calc(ans, left, right, op):
for i in range(26):
if op == '+':
ans[i] = left[i] + right[i]
else:
ans[i] = left[i] - right[i]
def dfs(root):
ans = [0] * 26
if not root:
return ans
if root.val in ['+', '-']:
left, right = dfs(root.left), dfs(root.right)
calc(ans, left, right, root.val)
else:
ans[ord(root.val) - ord('a')] += 1
return ans
return dfs(root1) == dfs(root2)/**
* Definition for a binary tree node.
* class Node {
* char val;
* Node left;
* Node right;
* Node() {this.val = ' ';}
* Node(char val) { this.val = val; }
* Node(char val, Node left, Node right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
private int[] counter;
public boolean checkEquivalence(Node root1, Node root2) {
counter = new int[26];
dfs(root1, 1);
dfs(root2, -1);
for (int n : counter) {
if (n != 0) {
return false;
}
}
return true;
}
private void dfs(Node root, int incr) {
if (root == null) {
return;
}
dfs(root.left, incr);
dfs(root.right, incr);
if (root.val != '+') {
counter[root.val - 'a'] += incr;
}
}
}/**
* Definition for a binary tree node.
* class Node {
* char val;
* Node left;
* Node right;
* Node() {this.val = ' ';}
* Node(char val) { this.val = val; }
* Node(char val, Node left, Node right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public boolean checkEquivalence(Node root1, Node root2) {
int[] ans1 = dfs(root1);
int[] ans2 = dfs(root2);
for (int i = 0; i < 26; ++i) {
if (ans1[i] != ans2[i]) {
return false;
}
}
return true;
}
private int[] dfs(Node root) {
int[] ans = new int[26];
if (root == null) {
return ans;
}
if (root.val == '+' || root.val == '-') {
int[] left = dfs(root.left);
int[] right = dfs(root.right);
calc(ans, left, right, root.val);
} else {
++ans[root.val - 'a'];
}
return ans;
}
private void calc(int[] ans, int[] left, int[] right, char op) {
for (int i = 0; i < 26; ++i) {
ans[i] = op == '+' ? left[i] + right[i] : left[i] - right[i];
}
}
}/**
* Definition for a binary tree node.
* struct Node {
* char val;
* Node *left;
* Node *right;
* Node() : val(' '), left(nullptr), right(nullptr) {}
* Node(char x) : val(x), left(nullptr), right(nullptr) {}
* Node(char x, Node *left, Node *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<int> counter;
bool checkEquivalence(Node* root1, Node* root2) {
counter.resize(26);
dfs(root1, 1);
dfs(root2, -1);
return count(counter.begin(), counter.end(), 0) == 26;
}
void dfs(Node* root, int incr) {
if (!root) return;
dfs(root->left, incr);
dfs(root->right, incr);
if (root->val != '+') counter[root->val - 'a'] += incr;
}
};/**
* Definition for a binary tree node.
* struct Node {
* char val;
* Node *left;
* Node *right;
* Node() : val(' '), left(nullptr), right(nullptr) {}
* Node(char x) : val(x), left(nullptr), right(nullptr) {}
* Node(char x, Node *left, Node *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
bool checkEquivalence(Node* root1, Node* root2) {
return dfs(root1) == dfs(root2);
}
vector<int> dfs(Node* root) {
vector<int> ans(26);
if (!root) return ans;
if (root->val == '+' || root->val == '-')
{
auto left = dfs(root->left);
auto right = dfs(root->right);
calc(ans, left, right, root->val);
return ans;
}
++ans[root->val - 'a'];
return ans;
}
void calc(vector<int>& ans, vector<int>& left, vector<int>& right, char op) {
for (int i = 0; i < 26; ++i)
ans[i] = op == '+' ? left[i] + right[i] : left[i] - right[i];
}
};