对称二叉树

leetCode–101（简单）

给你一个二叉树的根节点 root ， 检查它是否轴对称。

示例 1：

输入：root = [1,2,2,3,4,4,3]
输出：true

示例 2：

输入：root = [1,2,2,null,3,null,3]
输出：false

解法一：自己

哈哈哈哈，笑死了 我这算是什么解法~~

前序遍历，后序遍历，之后将后序遍历逆转，比较两个list是否相等。后来发现使用我这种方法，[1,2,2,null,3,null,3]这个用例过不去，因此将null值也加入了进去，瞎整~~过了。太菜了太菜了 不要看这个了 ，还是看大佬们的题解把

代码为：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
     TreeNode pre = new TreeNode();
    TreeNode last = new TreeNode();
    List<Integer> prelist = new ArrayList<>();
    List<Integer> laselist = new ArrayList<>();
    public boolean isSymmetric(TreeNode root) {
        if (root.left==null && root.right==null) return true;
        if (root.left==null || root.right==null) return false;
        pre = root;
        last = root;
        //前序排列
        if (pre!=null){
            preSort(pre);
        }
        //后序排序
        if (last!=null){
            lastSort(last);
        }
        Collections.reverse(laselist);
        return prelist.equals(laselist);
    }
    //前序遍历
    public void preSort(TreeNode root){
        if (root!=null){
            prelist.add(root.val);
            if (root.left!=null) preSort(root.left);
            else prelist.add(null);
            if (root.right!=null) preSort(root.right);
            else prelist.add(null);
        }
    }
    //中序遍历
    public void lastSort(TreeNode root){
        if (root!=null){
            if (root.left!=null) lastSort(root.left);
            else  laselist.add(null);
            if (root.right!=null) lastSort(root.right);
            else laselist.add(null);
            laselist.add(root.val);
        }
    }
}

解法二：递归

如果一个数是对称的，则左子树和右子树互为镜像。因此可以转化为，两个树在什么情况下互为镜像？

两个树互为镜像？

• 它们的两个根结点具有相同的值
• 每个树的右子树都与另一个树的左子树镜像对称

​ 也就是将一个树变成两个树进行比较。

代码为：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root==null) return true;
        //比较两个树是否互为镜像
        return check(root, root);
    }
    public boolean check(TreeNode p,TreeNode q){
        //都没有元素  说明相等
        if (p==null && q==null) return true;
        //一个有，一个没有  不相等
        if (p==null || q==null) return false;
        if (p.val==q.val) {
            //值相等  可以进行下一步比较
            return check(p.left,q.right) && check(p.right,q.left);
        }else return false;  //值不相等 直接return false
    }
}

解法三：迭代

将递归程序转换为迭代程序，最常用的方法就是引入一个队列。

代码为：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root==null) return true;
        if (root.left==null && root.right==null) return true;
        if (root.left==null || root.right==null) return false;
        //用队列保存节点
        Deque<TreeNode> deque = new LinkedList<>();
        //将左右节点加入队列中
        deque.addLast(root.left);
        deque.addLast(root.right);
        while (!deque.isEmpty()){
            //从队列中取出两个节点，再比较这两个节点
            TreeNode l = deque.removeFirst();
            TreeNode r = deque.removeFirst();
            //两个都为空值 则继续进行下面的比较， 两者有一个为空就返回false
            if (l==null && r==null) continue;
            if (l==null || r==null) return false;
            if (l.val!=r.val) return false;
            //值相等 继续进行下面的比较
            //将左节点的左孩子， 右节点的右孩子放入队列
            deque.addLast(l.left);
            deque.addLast(r.right);
            //将左节点的右孩子，右节点的左孩子放入队列	
            deque.addLast(l.right);
            deque.addLast(r.left);
        }
        return deque.isEmpty();
    }
}