Guys, do you have any idea how to solve it in O(N) ?

You are given 2 binary trees. You have to check, if they are similar. By similar, It means that left subtree of first tree is similar to left subtree of second tree (and the same for right). BUT they are similar also if left subtree of first tree is similar to right subtree of second tree and the other way aroung (right-left).