Description#
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:
![](https://spcdn.pages.dev/leetcode/problems/1612.Check%20If%20Two%20Expression%20Trees%20are%20Equivalent/images/tree1.png)
Input: root1 = [+,a,+,null,null,b,c], root2 = [+,+,a,b,c]
Output: true
Explanation: a + (b + c) == (b + c) + a
Example 3:
![](https://spcdn.pages.dev/leetcode/problems/1612.Check%20If%20Two%20Expression%20Trees%20are%20Equivalent/images/tree2.png)
Input: root1 = [+,a,+,null,null,b,c], root2 = [+,+,a,b,d]
Output: false
Explanation: a + (b + c) != (b + d) + a
Constraints:
- The number of nodes in both trees are equal, odd and, in the range
[1, 4999]
. Node.val
is '+'
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)?
Solutions#
Solution 1#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| # 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 dfs(root, v):
if root is None:
return
if root.val != '+':
cnt[root.val] += v
dfs(root.left, v)
dfs(root.right, v)
cnt = Counter()
dfs(root1, 1)
dfs(root2, -1)
return all(x == 0 for x in cnt.values())
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
| /**
* 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[] cnt = new int[26];
public boolean checkEquivalence(Node root1, Node root2) {
dfs(root1, 1);
dfs(root2, -1);
for (int x : cnt) {
if (x != 0) {
return false;
}
}
return true;
}
private void dfs(Node root, int v) {
if (root == null) {
return;
}
if (root.val != '+') {
cnt[root.val - 'a'] += v;
}
dfs(root.left, v);
dfs(root.right, v);
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
| /**
* 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) {
int cnt[26]{};
function<void(Node*, int)> dfs = [&](Node* root, int v) {
if (!root) {
return;
}
if (root->val != '+') {
cnt[root->val - 'a'] += v;
}
dfs(root->left, v);
dfs(root->right, v);
};
dfs(root1, 1);
dfs(root2, -1);
for (int& x : cnt) {
if (x) {
return false;
}
}
return true;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| /**
* Definition for a binary tree node.
* function Node(val, left, right) {
* this.val = (val===undefined ? " " : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {Node} root1
* @param {Node} root2
* @return {boolean}
*/
var checkEquivalence = function (root1, root2) {
const cnt = new Array(26).fill(0);
const dfs = (root, v) => {
if (!root) {
return;
}
if (root.val !== '+') {
cnt[root.val.charCodeAt(0) - 'a'.charCodeAt(0)] += v;
}
dfs(root.left, v);
dfs(root.right, v);
};
dfs(root1, 1);
dfs(root2, -1);
for (const x of cnt) {
if (x) {
return false;
}
}
return true;
};
|
Solution 2#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| # 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 dfs(root):
cnt = [0] * 26
if root is None:
return cnt
if root.val in '+-':
l, r = dfs(root.left), dfs(root.right)
k = 1 if root.val == '+' else -1
for i in range(26):
cnt[i] += l[i] + r[i] * k
else:
cnt[ord(root.val) - ord('a')] += 1
return cnt
return dfs(root1) == dfs(root2)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
| /**
* 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[] cnt1 = dfs(root1);
int[] cnt2 = dfs(root2);
for (int i = 0; i < 26; ++i) {
if (cnt1[i] != cnt2[i]) {
return false;
}
}
return true;
}
private int[] dfs(Node root) {
int[] cnt = new int[26];
if (root == null) {
return cnt;
}
if (root.val == '+' || root.val == '-') {
int[] l = dfs(root.left);
int[] r = dfs(root.right);
int k = root.val == '+' ? 1 : -1;
for (int i = 0; i < 26; ++i) {
cnt[i] += l[i] + r[i] * k;
}
} else {
cnt[root.val - 'a']++;
}
return cnt;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| /**
* 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) {
function<vector<int>(Node*)> dfs = [&](Node* root) -> vector<int> {
vector<int> cnt(26);
if (!root) {
return cnt;
}
if (root->val == '+' || root->val == '-') {
auto l = dfs(root->left);
auto r = dfs(root->right);
int k = root->val == '+' ? 1 : -1;
for (int i = 0; i < 26; ++i) {
cnt[i] += l[i] + r[i] * k;
}
} else {
cnt[root->val - 'a']++;
}
return cnt;
};
return dfs(root1) == dfs(root2);
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
| /**
* Definition for a binary tree node.
* function Node(val, left, right) {
* this.val = (val===undefined ? " " : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {Node} root1
* @param {Node} root2
* @return {boolean}
*/
var checkEquivalence = function (root1, root2) {
const dfs = root => {
const cnt = new Array(26).fill(0);
if (!root) {
return cnt;
}
if (root.val === '+' || root.val === '-') {
const l = dfs(root.left);
const r = dfs(root.right);
const k = root.val === '+' ? 1 : -1;
for (let i = 0; i < 26; ++i) {
cnt[i] = l[i] + k * r[i];
}
} else {
cnt[root.val.charCodeAt(0) - 'a'.charCodeAt(0)]++;
}
return cnt;
};
const cnt1 = dfs(root1);
const cnt2 = dfs(root2);
for (let i = 0; i < 26; ++i) {
if (cnt1[i] !== cnt2[i]) {
return false;
}
}
return true;
};
|