Algorithm-LeetCode/Solutions/1612.Check_If_Two_Expression_Trees_are_Equivalent.py at main · ling67/Algorithm-LeetCode · GitHub

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
"""
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.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)?

"""

# 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, cnter):
            if not root:
                return
            if root.val.isalpha():
                cnter[root.val] += 1
            dfs(root.left, cnter)
            dfs(root.right, cnter)

        cnter1 = defaultdict(int)
        cnter2 = defaultdict(int)
        dfs(root1, cnter1)
        dfs(root2, cnter2)
        return cnter1 == cnter2

"""
Solution 2:it should be support the - sign
"""

# 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:

        values = collections.defaultdict(int)

        def helper(node, operator):

            if not node: return None

            helper(node.left, operator)
            helper(node.right, operator)

            if operator == "+":
                values[node.val] += 1
            elif operator == "-":
                values[node.val] -= 1

        helper(root1, "+")
        helper(root2, "-")

        return all(values[key] == 0 for key in values if key != "+")