LeetCode 1612: Check If Two Expression Trees are Equivalent

Explanation:

To check if two expression trees are equivalent, we need to compare their structures as well as the values of the nodes. We can perform a recursive traversal of the trees and compare the nodes at each step. If the nodes are both operators, we compare their values and recursively check their left and right children. If the nodes are operands, we simply compare their values. If the structures and values of the trees match, the trees are considered equivalent.

Algorithm:

1. Implement a recursive function that takes two nodes as input and checks if they are equivalent.
2. If both nodes are operators, compare their values and recursively check their left and right children.
3. If both nodes are operands, compare their values.
4. If the structures and values of the nodes match recursively, the trees are considered equivalent.

Time Complexity:

The time complexity of this algorithm is O(n), where n is the number of nodes in the expression trees.

Space Complexity:

The space complexity of this algorithm is O(h), where h is the height of the expression trees.

:

// Java Solution
class Solution {
    public boolean checkEquivalence(Node root1, Node root2) {
        Map<Character, Integer> map = new HashMap<>();
        updateMap(root1, map, 1);
        updateMap(root2, map, -1);
        for (int count : map.values()) {
            if (count != 0) {
                return false;
            }
        }
        return true;
    }
    
    private void updateMap(Node node, Map<Character, Integer> map, int value) {
        if (node == null) {
            return;
        }
        if (node.val != '+') {
            map.put(node.val, map.getOrDefault(node.val, 0) + value);
        }
        updateMap(node.left, map, value);
        updateMap(node.right, map, value);
    }
}