LeetCode101.对称二叉树

题目描述

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

示例

提条的代码

import java.util.List;
import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Collections;
class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root==null)return true;
        List<List<Integer>> leftTree=levelOrder(root.left);
        List<List<Integer>> rightTree=levelOrder(root.right);
        if(leftTree.size()!=rightTree.size())return false;
        for(int i=0;i<leftTree.size();i++){
            List<Integer> leftCurrentLevel=leftTree.get(i);
            List<Integer> rightCurrentLevel=rightTree.get(i);
            Collections.reverse(leftCurrentLevel);
            if(!leftCurrentLevel.equals(rightCurrentLevel))return false;
        }
        return true;
    }

    public List<List<Integer>> levelOrder(TreeNode root){
        TreeNode cur=root;
        Deque<TreeNode> queue=new LinkedList<>();
        List<List<Integer>> result= new ArrayList<>();
        //剪枝处理
        if(root==null)return result;
        TreeNode temp=null;
        //初始化队列
        queue.offer(cur);
        while(!queue.isEmpty()){
            //当前层的树节点数量
            int count=queue.size();
            List<Integer> list=new ArrayList<>();
            //count到0意味着当前层遍历结束
            while(count>0){
                count--;
                temp=queue.poll();
                if(temp==null){
                    list.add(Integer.MIN_VALUE);
                    continue;
                }
                list.add(temp.val);
                queue.offer(temp.left);
                queue.offer(temp.right);
            }
            result.add(list);
        }
        return result;
    }
}

我的想法很简单，分给从根的左子树和右子树层序遍历，遍历出来的两颗树的当前层的内容依次进行取反比较(左子树或右子树其中一个进行取反比较就行)，如果这个过程全部都通过那就返回true，否则返回false。

学习到的内容

由于我的方法跑出来的结果不太好，所以找了大佬们的方法来看，发现递归方法是最优方法，迭代法倒不是那么高效。
递归法：

咳，懒得电脑画图，就用笔画了。
从下面的代码开始说起，递归到最后一个节点(也是第一个执行递归主代码的节点)一定是图中标出的①的值为5的节点，左侧5的左节点和右侧5的右节点都是空，返回true，继而判断左侧5的右节点和右侧5的左节点，也都是true，所以左右5节点返回true；然后递归至上一层就会判断②对应的两个6是否对称，也返回true，所以左右两个3的左右子树是对称的，然后递归至上一层的两个4，判断③和④过程。一直递归值根节点1。

import java.util.List;
import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Collections;
class Solution {
    public boolean isSymmetric(TreeNode root) {
        return recursiveMethod(root.left,root.right);
    }

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

迭代法：
队列实现的迭代法是一层层地去判断是否对称的，我这里的顺序是左侧的左节点和右侧的右节点进行对称判断然后再判断左侧的右节点和右侧的左节点。过程就不赘述了，看下代码就知道，而且迭代法的执行效率不高其实。

import java.util.List;
import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Collections;
class Solution {
    public boolean isSymmetric(TreeNode root) {
        Deque<TreeNode> queue = new LinkedList<>();
        TreeNode left = root.left;
        TreeNode right = root.right;
        queue.offer(left);
        queue.offer(right);
        while(!queue.isEmpty()){
            left=queue.poll();
            right=queue.poll();
            if(left==null&&right==null)continue;

            //左右一个节点不为空，或者都不为空但数值不同，返回false
            if((left==null&&right!=null)||(left!=null&&right==null)||left.val!=right.val)return false;
            queue.offer(left.left);
            queue.offer(right.right);
            queue.offer(left.right);
            queue.offer(right.left);
        }

        return true;
    }
}