1612. Check If Two Expression Trees are Equivalent
Last updated
Last updated
https://leetcode.com/problems/check-if-two-expression-trees-are-equivalent
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:
Example 2:
Example 3:
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.