alt alt alt

//方法一：层序遍历
//注释一：
/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
import java.util.*;
class Solution {
    int INF = 0x3f3f3f3f;    //INF为无效值，用于识别空节点，因为list是整数列表，不能有null
    TreeNode emptyNode = new TreeNode(INF);    //空节点emptyNode，emptyNode.val = INF
    boolean i+sSymmetrical(TreeNode root) {
        if (root == null) 
            return true;    //根节点为空，返回对称
        //cur表示当前所指向的位置；
        //first表示当前数组中头的位置；
        //last表示当前数组中尾的位置
        Deque<TreeNode> d = new ArrayDeque<>();    //Deque双端队列
        d.add(root);    //root节点入队
        //当满足队列不为空时
        while (!d.isEmpty()) {
            // 每次循环都将下一层拓展完并存到「队列」中
            // 同时将该层节点值依次存入到「临时列表」中
            int size  = d.size();    //队列长度
            List<Integer> list = new ArrayList<>();    //定义数组链表
            
            //当满足队列长度自减（先比较再自减），用于控制一层一层检查
            while (size-- > 0) {
                TreeNode poll = d.pollFirst();    //弹出元素
                //弹出元素不为空节点
                if (!poll.equals(emptyNode)) {
                    //弹出节点左子树添加到队列末尾，左子树不为空，添加左子树；否则，添加空节点
                    d.addLast(poll.left != null ? poll.left : emptyNode);
                    //弹出节点右子树，添加至队列末尾，右子树不为空，添加右子树；否则，添加空节点
                    d.addLast(poll.right != null ? poll.right : emptyNode);
                }
                //弹出的节点的值添加至列表中
                list.add(poll.val);
            }

            // 每一层拓展完后，检查一下存放当前层的该层是否符合「对称」要求
            if (!check(list)) return false;
        }
        return true;
    }

    // 使用「双指针」检查某层是否符合「对称」要求
    boolean check(List<Integer> list) {
        int l = 0, r = list.size() - 1;    //定义列表首尾两个指针
        //满足左指针小于右指针，遍历
        while (l < r) {
            if (!list.get(l).equals(list.get(r))) 
                return false;
            l++;
            r--;
        }
        return true;
    }
}

//方法一：层序遍历
//注释二：
/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
import java.util.*;
public class Solution {
    boolean isSymmetrical(TreeNode pRoot) {
        //查询树是否对称
        
        //首先把根节点放入队列中
        //两个循环，一个是检查队列是否为空，一个是检查树各层放入队列的元素长度是是否零
        //外循环检查队列不为空，然后获取树该层放入队列中的元素长度，接着定义一个存放弹出元素的值的数组列表
            //内循环检查树该层在队列中的元素是否弹出完，然后将获取弹出的元素，判断弹出的元素不为空，将弹出元素的左右子树压入队列中，
            //如果子树为空则，则压入空节点
            //把弹出的元素放入列表中
            //树该层在队列中的元素长度不为零，继续循环，若为零，则跳出内循环
        //调用判断列表元素是否对称的方法，判断列表中的元素是否对称，对称就继续循环，判断队列是否为空，接着判断树的下一层是否对称
        
    //（双指针）判断列表是否对称
        //定义空节点用整数表示
        //INF为无效值，用于识别空节点，因为list是整数列表，不能有null
        int INF = 0x3f3f3f3f;
        TreeNode emptyNode = new TreeNode(INF);

        if(pRoot == null)
            return true;
        
        Deque<TreeNode> q = new ArrayDeque<>();
        q.add(pRoot);
        
        while(!q.isEmpty()){
            int size = q.size();
            List<Integer> list = new ArrayList<>();
            
            while(size-->0){
                TreeNode node = q.pollFirst();
                //不能使用node != emptyNode    !node.equals(emptyNode)
                if(node != emptyNode){
                    q.addLast(node.left == null?emptyNode:node.left);
                    q.addLast(node.right == null?emptyNode:node.right);
                }
                list.add(node.val);
            }
            if(!check(list))
                return false;
        }
        return true;
    }
    //列表<Integer>这个约束条件不能漏
    boolean check(List<Integer> list){
        int l = 0;
        int r = list.size()-1;

        while(l<r){
             //    比较两个数组里的元素是否相等可以使用Arrays类调用equals()方法进行比较。不能用==比较，
             //    ==比的是两个数组对象的地址，如果是两个不同的对象，结果会一直是false .
            //if(list.get(l) != list.get(r))    //error
            if(!list.get(l).equals(list.get(r)))
                return false;
            ++l;
            --r;
        }
        return true;
    }
}

//方法二：递归
class Solution {
    public boolean isSymmetrical(TreeNode root) {
        return check(root, root);
    }
    boolean check(TreeNode a, TreeNode b) {
        if (a == null && b == null) return true;    //a和b都为null才成立
        //本来下面有三个种可能使得判断成立
        //a和b都为空； a为空，b不为空； a不为空， b为空
        //进入下面判断，说明上面的a和b不都为null,故下面只有两种可能
        //a为空，b不为空
        //a不为空，b为空，这样判断才成立
        if (a == null || b == null) return false;
        if (a.val != b.val) return false;    //a和b都不为空，但值不同，判断成立
        //最后是a和b都不为空，且值相同
        //最好是画出递归树，从底向上return思考即可
        return check(a.left, b.right) && check(a.right, b.left);
    }
}