题目描述

给定一个二叉树，检查它是否是镜像对称的。

样例

例如，二叉树 [1,2,2,3,4,4,3] 是对称的。

    1
   / \
  2   2
 / \ / \
3  4 4  3

但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:

    1
   / \
  2   2
   \   \
   3    3

进阶：

你可以运用递归和迭代两种方法解决这个问题吗？

算法分析

一颗镜像树满足以下情况

• 1、空树为镜像树
• 2、非空树时，对于左右子树 left 和 right 有
  • （1）左右子树都为空， left == NULL && right == NULL
  • （2）左右子树不为空，则左右子树的值相同，即 left->val == right->val
    且left的左子树和right的右子树镜像对称，left的右子树和right的左子树镜像对称，
• 3、其他情况不是镜像树

时间复杂度 $O(n)$

Java 代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    static boolean dfs(TreeNode l,TreeNode r)
    {
        if(l == null && r == null) return true;
        if(l == null || r == null) return false;
        if(l.val != r.val) return false;
        return dfs(l.left,r.right) && dfs(l.right,r.left);
    }
    public boolean isSymmetric(TreeNode root) {
        return dfs(root,root);
    }
}