tweaked-identical-binary-tree

Time Complexity:

(a, b)
O(1) / | | \
O(4)

O(4^(logn - 1))

All together O(4^logn) ~ n^2

public boolean isTweakedIdentical(TreeNode a, TreeNode b) {

if (a == null && b == null) return true;

if (a == null || b == null) return false;

if (a.val != b.val) return false;

//The next level can either be identical or symmetric

return isTweakedIdentical(a.left, b.left) && isTweakedIdentical(a.right, b.right) ||

isTweakedIdentical(a.left, b.right) && isTweakedIdentical(a.right, b.left);

}