一. 题目

二. 思路

1. 反向递归

• 分别对根的左右儿子，进行根左右、根右左进行遍历，存储遍历的节点，最后比较两个集合即可。

2. 同步递归

3. 迭代

• 将方法二改为迭代。

• 

三. 代码

1. 反向递归

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
{
    static final int INF = Integer.MAX_VALUE;
    final List<Integer> lL = new ArrayList<>(), rL = new ArrayList<>();

    //根左右
    void dfsL(TreeNode u)
    {
        lL.add(u.val);
        TreeNode ls = u.left, rs = u.right;
        if (ls == null) lL.add(INF);
        else dfsL(ls);

        if (rs == null) lL.add(INF);
        else dfsL(rs);
    }

    //根右左
    void dfsR(TreeNode u)
    {
        rL.add(u.val);
        TreeNode ls = u.left, rs = u.right;
        if (rs == null) rL.add(INF);
        else dfsR(rs);

        if (ls == null) rL.add(INF);
        else dfsR(ls);
    }

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

        dfsL(root.left);
        dfsR(root.right);
        return lL.equals(rL);
    }
}

2. 同步递归

class Solution
{
    boolean dfs(TreeNode ls, TreeNode rs)
    {
        if (ls == null && rs == null) return true;
        if (ls == null || rs == null) return false;
        return ls.val == rs.val && dfs(ls.left, rs.right) && dfs(ls.right, rs.left);
    }

    public boolean isSymmetric(TreeNode root)
    {
        return dfs(root, root);
    }
}

3. 迭代

class Solution
{
    Deque<TreeNode> q = new LinkedList<>();//ArrayDeque不能加入null

    public boolean isSymmetric(TreeNode root)
    {
        TreeNode u, v;
        q.offer(root);
        q.offer(root);
        while (!q.isEmpty())
        {
            u = q.poll();
            v = q.poll();
            if (u == null && v == null) continue;
            if (u == null || v == null || u.val != v.val) return false;
            
            q.offer(u.left);
            q.offer(v.right);

            q.offer(u.right);
            q.offer(v.left);
        }

        return true;
    }
}