Check If Two Expression Trees are Equivalent
给一个只有+和字符的算式树, 问结果是不是一样?
因为只有+, 所以有交换律, 所以只需要counting即可.
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 |
/** * 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 { public boolean checkEquivalence(Node root1, Node root2) { int[] count1 = new int[26]; int[] count2 = new int[26]; count(count1, root1); count(count2, root2); for(int i = 0; i < 26; i++) { if(count1[i] != count2[i]) return false; } return true; } private void count(int[] count, Node node) { if(node == null) return; if(node.val != '+') count[node.val - 'a']++; count(count, node.left); count(count, node.right); } } |