Question

Formatted question description: https://leetcode.ca/all/1612.html


 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.

Algorithm

Just count the type and number of letters in the two expression trees. Because it’s + only, (a+b)+c is same as a+(b+c)

Code

Java

public class Check_If_Two_Expression_Trees_are_Equivalent {

    public class Solution {
        public boolean checkEquivalence(Node root1, Node root2) {

            int[] count = new int[26];

            dfs(root1, count, 1);
            dfs(root2, count, -1);

            for (int i = 0; i < count.length; i++) {
                if (count[i] != 0) {
                    return false;
                }
            }

            return true;
        }

        private void dfs(Node cur, int[] count, int diff) {
            if (cur == null) {
                return;
            }

            if (cur.val != '+') {
                count[cur.val - 'a'] += diff;
            }

            dfs(cur.left, count, diff);
            dfs(cur.right, count, diff);
        }
    }

    class Node {
        char val;
        Node left, right;

        public Node(char val) {
            this.val = val;
        }
    }

}

Follow up: What will you change in your solution if the tree also supports the ‘-‘ operator (i.e. subtraction). Then use 2 maps, one for + records, and one for - records.

    // if '-' supported, then it's just (-1*X)
    // 2 maps, one for + , and one for -
    class Solution_followup {
        public boolean checkEquivalence(Node root1, Node root2) {

            int[] countPlus = new int[26];
            int[] countMinus = new int[26];


            dfs(root1, countPlus, countMinus, 1, false);
            dfs(root2, countPlus, countMinus, -1, false);

            for (int i = 0; i < countPlus.length; i++) {
                if (countPlus[i] != 0) {
                    return false;
                }
            }

            for (int i = 0; i < countMinus.length; i++) {
                if (countMinus[i] != 0) {
                    return false;
                }
            }

            return true;
        }

        private void dfs(Node cur, int[] countPlus, int[] countMinus, int diff, boolean isRightChildOfMinusNode) {
            if (cur == null) {
                return;
            }

            if (cur.val == '+') {
                dfs(cur.left, countPlus, countMinus, diff, false);
                dfs(cur.right, countPlus, countMinus, diff, false);
            } else if (cur.val == '-') {
                dfs(cur.left, countPlus, countMinus, diff, false);
                dfs(cur.right, countPlus, countMinus, diff, true);
            } else {
                if (isRightChildOfMinusNode) {
                    countMinus[cur.val - 'a'] += diff;
                } else {
                    countPlus[cur.val - 'a'] += diff;
                }
            }
        }
    }

All Problems

All Solutions