题解 | #对称的二叉树#

import java.util.*;
/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

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

    }

}
*/
// 队列层次遍历，双队列判断回文
// java中队列的两种实现：LinkedList可以有null元素，ArrayDeque不可以
// 时空复杂度：O（n）
public class Solution {
    boolean isSymmetrical(TreeNode pRoot) {
        if (pRoot == null)
            return true;
        Queue<TreeNode> leftQ = new LinkedList<>();
        Queue<TreeNode> rightQ = new LinkedList<>();
        leftQ.add(pRoot.left);
        rightQ.add(pRoot.right);
        while (!leftQ.isEmpty() && !rightQ.isEmpty()){
            TreeNode node1 = leftQ.poll();
            TreeNode node2 = rightQ.poll();
            if (node1 == null && node2 != null)
                return false;
            if (node1 != null && node2 == null)
                return false;
            if (node1 == null && node2 == null)
                continue;
            if (node1.val != node2.val)
                return false;
            leftQ.add(node1.left);
            leftQ.add(node1.right);
            rightQ.add(node2.right);
            rightQ.add(node2.left);
        }
        return true;
    }
}