LintCode 469, 470 - Tweaked Identical Binary Tree

https://github.com/shawnfan/LintCode/blob/master/Java/Tweaked%20Identical%20Binary%20Tree.java
http://www.jianshu.com/p/0623cf8ad71b

检查两棵二叉树是否在经过若干次扭转后可以等价。扭转的定义是，交换任意节点的左右子树。等价的定义是，两棵二叉树必须为相同的结构，并且对应位置上的节点的值要相等。
注意：你可以假设二叉树中不会有重复的节点值。

样例

    1             1
   / \           / \
  2   3   and   3   2
 /                   \
4                     4

是扭转后可等价的二叉树。

    1             1
   / \           / \
  2   3   and   3   2
 /             /
4             4

就不是扭转后可以等价的二叉树。

Check two given binary trees are identical or not. Assuming any number of tweaks are allowed.
A tweak is defined as a swap of the children of one node in the tree.
Example
    1             1
   / \           / \
  2   3   and   3   2
 /                   \
4                     4
are identical.
    1             1
   / \           / \
  2   3   and   3   4
 /                   \
4                     2
are not identical.
Note
There is no two nodes with the same value in the tree.
Challenge
O(n) time

Recursive 比对左左,左右,右左，右右

• Recursion - 递归求解，分治的思路。
• 注意，题目中说的是经过若干次扭转后可以等价，所以不要忘记考虑完全identical的情况，某一个节点的左右子树翻转一次对称，反转两次还原。

https://yisuang1186.gitbooks.io/java-/content/tweaked_identical_binary_tree.html

不要忘记a.val == b.val这个条件

    public boolean isTweakedIdentical(TreeNode a, TreeNode b) {
        // Write your code here
        if (a == null && b == null) {
            return true;
        }
        if (a == null || b == null) {
            return false;
        }
        if (a.val != b.val) {
            return false;
        }
        return (isTweakedIdentical(a.left, b.left) && isTweakedIdentical(a.right, b.right) ) || (isTweakedIdentical(a.left, b.right) && isTweakedIdentical(a.right, b.left) );
    }

public boolean isTweakedIdentical(TreeNode a, TreeNode b) {
    if (a == null || b == null) {
        return a == null && b == null;
    }
    if (a.val != b.val) {
        return false;
    }
    return (isTweakedIdentical(a.left, b.left) && isTweakedIdentical(a.right, b.right))
        || (isTweakedIdentical(a.left, b.right) && isTweakedIdentical(a.right, b.left));
}
https://www.lintcode.com/en/problem/identical-binary-tree/
Check if two binary trees are identical. Identical means the two binary trees have the same structure and every identical position has the same value.

    1             1
   / \           / \
  2   2   and   2   2
 /             /
4             4

are identical.

    1             1
   / \           / \
  2   3   and   2   3
 /               \
4                 4

are not identical.

https://yixuanwangblog.wordpress.com/2016/09/04/lintcode-469-identical-binary-tree/
http://www.geeksforgeeks.org/write-c-code-to-determine-if-two-trees-are-identical/
http://www.jiuzhang.com/solutions/identical-binary-tree/

    public boolean isIdentical(TreeNode a, TreeNode b) {
        // Write your code here
        if (a == null && b == null)
            return true;
        if (a != null && b != null) {
            return a.val == b.val && isIdentical(a.left, b.left)
                    && isIdentical(a.right, b.right);
        }
        return false;
    }

https://xuezhashuati.blogspot.com/2016/02/identical-binary-tree.html

    public boolean isIdentical(TreeNode a, TreeNode b) {
        // Write your code here
        if (a == null && b == null) {
            return true;
        }
        
        if ((a == null && b != null) || (a != null && b == null)) {
            return false;
        } 
        
        if (a != null && b != null) {
            if (a.val != b.val) {
                return false;
            }
            else {
                return isIdentical(a.left, b.left) && isIdentical(a.right, b.right);
            }
        }
        
        return false;
    }