[LeetCode] 1612 Check If Two Expression Trees are Equivalent

1612. Check If Two Expression Trees are Equivalent

Medium

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.

Follow up: What will you change in your solution if the tree also supports the '-' operator (i.e. subtraction)?

 

Example 1:

Input: root1 = [x], root2 = [x]
Output: true

Example 2:

Input: root1 = [+,a,+,null,null,b,c], root2 = [+,+,b,c,a]
Output: true
Explaination: a + (b + c) == (b + c) + a

Example 3:

Input: root1 = [+,a,+,null,null,b,c], root2 = [+,+,b,d,a]
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.

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. * 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 { int[] cnt = new int[26]; public boolean checkEquivalence(Node root1, Node root2) { helper(root1, true); helper(root2, false); for(int i=0; i<26; ++i){ if(cnt[i]>0) return false; } return true; } void helper(Node root, boolean add){ if(root==null) return; helper(root.left, add); helper(root.right, add); if(root.left==null && root.right==null){ cnt[root.val-'a'] += add?1:-1; } } }

https://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=677356&extra=page%3D1%26filter%3Dsortid%26sortid%3D311%26searchoption%255B3088%255D%255Bvalue%255D%3D12%26searchoption%255B3088%255D%255Btype%255D%3Dradio%26searchoption%255B3046%255D%255Bvalue%255D%3D1%26searchoption%255B3046%255D%255Btype%255D%3Dradio%26orderby%3Ddateline&page=1

 

判断两个树是否表达同一个数学表达式，树叶可以为数字，字母，+-*, 类似类似preorder traverse来表示表达式。 

第二题就是前序周游序列化城字符串，比较字符串即可？还是我想简单了。楼主给个例子？