剑指 Offer 26. 树的子结构 & 27. 二叉树的镜像 & 28. 对称的二叉树

26题目描述：

输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)

B是A的子结构，即 A中有出现和B相同的结构和节点值。

例如: 给定的树 A:

给定的树 B：

   4 
  /
 1

返回 true，因为 B 与 A 的一个子树拥有相同的结构和节点值。

解析：

1.首先如果A或者B为空，直接返回false，因为题目约定空树不是任意一个树的子结构
2.然后去判断几种情况，
（1）A的根节点和B的根节点相同的情况，依次比较它们的子节点
（2）A的根节点和B的根节点不相同的情况，A的左子树和B的根节点进行比较
（3）A的根节点和B的根节点不相同的情况，A的右子树和B的根节点进行比较
3.创建辅助函数
（1）遍历完B，直到为空，说明B的全部节点都和A的子结构匹配上，返回true
（2）A的节点为空，但B的节点不为空，说明不匹配，返回false
（3）A和B都不为空，但数值不同，说明不匹配，返回false
（4）此时，当这个点时匹配的，继续递归去判断左子树和右子树是否分别匹配

Java:

public boolean isSubStructure(TreeNode A, TreeNode B) {
        if(A == null || B == null) {
            return false;
        }
        return isSub(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B);
    }
    boolean isSub(TreeNode A, TreeNode B) {
        if(B == null) {
            return true;
        }
        if(A == null || A.val != B.val) {
            return false;
        }
        return isSub(A.left, B.left) && isSub(A.right, B.right);
    }

JavaScript:

var isSubStructure = function(A, B) {
    if(A === null || B === null) {
        return false;
    }
    function isSub(A, B) {
        if(B === null) {
            return true;
        }
        if(A === null || A.val !== B.val) {
            return false;
        }
        return isSub(A.left, B.left) && isSub(A.right, B.right);
    }
    return isSub(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B);
};

27题目描述：

请完成一个函数，输入一个二叉树，该函数输出它的镜像。

例如输入：

     4
   /   \
  2     7
 / \   / \
1   3 6   9

镜像输出：

     4
   /   \
  7     2
 / \   / \
9   6 3   1

解析：

1.当节点为空时，直接返回空
2.设置一个临时节点temp，用来存储当前节点的左子树
3.以下有两个操作是交换当前节点的左右子树
当前节点的左子树为节点的右子树，同时递归下去，不停的交互子树中的节点
当前节点的右子树为节点的左子树，同时递归下去，不停的交互子树中的节点
4.最后返回根节点

Java:

public TreeNode mirrorTree(TreeNode root) {
        if(root == null) {
            return null;
        }
        TreeNode ans = new TreeNode(root.val);
        ans.left = mirrorTree(root.right);
        ans.right = mirrorTree(root.left);
        return ans;
    }

JavaScript:

var mirrorTree = function(root) {
    if(root === null) {
        return null;
    }
    let temp = root.left;
    root.left = mirrorTree(root.right);
    root.right = mirrorTree(temp);
    return root;
};

28题目描述：

请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。

例如，二叉树 [1,2,2,3,4,4,3] 是对称的，则返回true

但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的，则返回false

解析：

1.边界情况，如果根节点为空，则返回true
2.递归判断左子树和右子树是否对称
3.创建辅助函数去判断
（1）如果某根子树的左右两子树同时为空，则肯定是对称的，直接返回true
（2）如果根子树的左右两子树有某子树为空，某子树有值，则不对称，返回false
（3）左子树的值与右子树的值不相等，不对称，返回false
（4）递归的对比当前节点的左子树的左子树与右子树的右子树、左子树的右子树与右子树的左子树是否对称

Java:

public boolean isSymmetric(TreeNode root) {
        if(root == null) {
            return true;
        }
        return isSymmetriacalCor(root.left, root.right);
    }
    private boolean isSymmetriacalCor(TreeNode L, TreeNode R) {
        if(L == null && R == null) {
            return true;
        }
        if(L == null || R == null) {
            return false;
        }
        if(L.val != R.val) {
            return false;
        }
        return isSymmetriacalCor(L.left, R.right) && isSymmetriacalCor(L.right, R.left);
    }

JavaScript:

var isSymmetric = function(root) {
    if(root === null) {
        return true;
    }
    return isSymmetriacalCor(root.left, root.right);

    function isSymmetriacalCor(L, R) {
        if(L === null && R === null) {
            return true;
        }
        if(L === null || R === null) {
            return false;
        }
        if(L.val !== R.val) {
            return false;
        }
        return isSymmetriacalCor(L.left, R.right) && isSymmetriacalCor(L.right, R.left);
    }
};