Tree
Depth-First Search
Hash Table
Binary Tree
Counting
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:
Input: root1 = [+,a,+,null,null,b,c], root2 = [+,+,a,b,c]
Output: true
Explanation : a + (b + c) == (b + c) + a
Example 3:
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
Python3 Java C++ JavaScript
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
Python3 Java C++ JavaScript
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 ;
};
GitHub