Check If Two Binary Tree Are Similar

题目地址：
https://instant.1point3acres.com/thread/199216

题目：
即root要相等, left/right可以交换. “交换”可以进行多次.

case1:

     5
   /   \
  2     4
 / \   / \
1  3 null 6

     5
   /   \
  2     4
 / \   / \
1  3  6  null

case2: 

     5
   /   \
  4     2
 / \   / \
1  3 null 6

     5
   /   \
  2     4
 / \   / \
1  3  6  null

这道题需要考虑的情况case1, case2两种情况。

代码：

public class CheckIfTwoBinaryTreeAreSimilar {

    public boolean isSimilar(TreeNode p, TreeNode q){
        if(p == null && q == null){
            return true;
        }
        else if(p != null && q != null){
            if(p.val == q.val){
                return (isSimilar(p.left, q.left) && isSimilar(p.right, q.right)) ||
                        compareSwap(p, q);
            }
        }
        return false;
    }

    private boolean compareSwap(TreeNode p, TreeNode q) {
        if(p.left != null && p.right != null && q.left != null && q.right != null){
            int left = p.left.val;
            p.left.val = p.right.val;
            p.right.val = left;

            // here is important, otherwise it will overflow            if(p.left.val != q.left.val || p.right.val != q.right.val){
                return false;
            }
            return isSimilar(p, q);
        }
        else if(((p.left == null && p.right != null) || (p.left != null && p.right == null)) && ((q.left == null && q.right != null) || (q.left != null && q.right == null))){
            if(p.left == null){

                // here is important, otherwise it will overflow                if(p.right.val != q.left.val){
                    return false;
                }
                p.left = p.right;
                p.right = null;
            }
            else{

                // here is important, otherwise it will overflow                if(p.left.val != q.right.val){
                    return false;
                }
                p.right = p.left;
                p.left = null;
            }
            return isSimilar(p, q);
        }
        return false;
    }

    public static void main(String[] args){
        TreeNode node51 = new TreeNode(5);
        TreeNode node21 = new TreeNode(2);
        TreeNode node41 = new TreeNode(4);
        TreeNode node11 = new TreeNode(1);
        TreeNode node31 = new TreeNode(3);
        TreeNode node61 = new TreeNode(6);
        node51.left = node21;
        node51.right = node41;
        node21.left = node11;
        node21.right = node31;
        node41.right = node61;

        TreeNode node52 = new TreeNode(5);
        TreeNode node22 = new TreeNode(2);
        TreeNode node42 = new TreeNode(4);
        TreeNode node32 = new TreeNode(3);
        TreeNode node12 = new TreeNode(1);
        TreeNode node62 = new TreeNode(6);
        node52.left = node22;
        node52.right = node42;
        node22.left = node32;
        node22.right = node12;
        node42.left = node62;

        CheckIfTwoBinaryTreeAreSimilar checkIfTwoBinaryTreeAreSimilar = new CheckIfTwoBinaryTreeAreSimilar();
        boolean rst = checkIfTwoBinaryTreeAreSimilar.isSimilar(node51, node52);
        System.out.println(rst);


    }

}