101. 对称二叉树：DFS + BFS.md

题目简述：

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

题目链接：101. 对称二叉树

思路

总的来说就是忽视根节点，检查根节点的左右子树是否镜像对称。

检查镜像对称的办法是同时对两棵子树进行DFS或BFS，当考察其中一棵子树的left时我们同时考察另一棵子树的right，当考察其中一棵子树的right时我们同时考察另一棵子树的left，即镜像对称。

DFS

/**
 * 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) {
        return dfs(root, root);
    }

    public boolean dfs(TreeNode a, TreeNode b) {
        if ((a == null && b != null) || (a != null && b == null)) return false;
        
        if (a == null && b == null) return true;
        
        if (a.val != b.val) return false;

        if (a.left == null && b.right == null && a.right == null && b.left == null) return true;

        boolean res1 = dfs(a.left, b.right);
        boolean res2 = dfs(a.right, b.left);

        return res1 && res2;
    }
}

BFS

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null || (root.left == null && root.right == null)) return true;
        if ((root.left != null && root.right == null) || (root.left == null && root.right != null)) return false;

        Deque<TreeNode> queueA = new ArrayDeque<>();
        Deque<TreeNode> queueB = new ArrayDeque<>();
        queueA.offer(root.left);
        queueB.offer(root.right);

        while (!queueA.isEmpty() && !queueB.isEmpty()) {
            TreeNode a = queueA.poll();
            TreeNode b = queueB.poll();

            if (a.val != b.val) return false;

            if (a.left != null && b.right != null) {
                queueA.offer(a.left);
                queueB.offer(b.right);
            } else if (!(a.left == null && b.right == null)) {
                return false;
            }

            if (a.right != null && b.left != null) {
                queueA.offer(a.right);
                queueB.offer(b.left);
            } else if (!(a.right == null && b.left == null)) {
                return false;
            }
        }

        return true;
    }
}