[数据结构与算法]剑指 Offer 28. 对称的二叉树(JavaScript语言)

思路一（菜鸡版：利用前两题的函数）

前两题写了两个函数。一个是mirrorTree(root)，求二叉树的镜像树。一个是recur(A, B)，判断二叉树B是否是二叉树A的子结构，规定A的根节点必须和B的根节点相同。
（PS：这里也可以用【剑指 Offer 26. 树的子结构】这题的isSubStructure(A, B)函数，只不过这个函数也包含了recur函数，recur函数也可以实现本题）

判断条件:如果该二叉树记作A，该二叉树的镜像树记作B，如果A是B的子结构，那么A就是对称的二叉树。

代码

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isSymmetric = function(root) {
    var mirrorTree = function(root) {//函数功能:求二叉树的镜像树
    if(root && root.left == null && root.right == null) return new TreeNode(root.val);
    if(!root) {
        return root;
    }else {
        var tree = new TreeNode(root.val);
        tree.right = mirrorTree(root.left);
        tree.left = mirrorTree(root.right);
        return tree;
    }
};
    
    var recur = function(A, B) {//函数功能：判断二叉树B是否是二叉树A的子结构，规定A的根节点必须和B的根节点相同
        if(!B) return true;
        if(!A) return false;
        if(A.val != B.val) return false;
        return recur(A.left, B.left)&&recur(A.right, B.right);
    }
     if(!root) return true;
     else {
         if(recur(root, mirrorTree(root))) return true;//如果该二叉树是二叉树的镜像树的子结构，那么他就是对称的二叉树
         else return false;
     }
     
};

思路二（递推法）

思路参考自：面试题28. 对称的二叉树（递归，清晰图解）

代码

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isSymmetric = function(root) {
    var recur = function(L, R) {//判断L和R是不是对称二叉树
        if(!L && !R) return true;
        if(!L || !R || L.val != R.val) return false;
        return recur(L.left, R.right) && recur(L.right, R.left);
    }
    if(!root) return true;
    return recur(root.left,root.right);
    
};