## 题目地址(101. 对称二叉树)

https://leetcode-cn.com/problems/symmetric-tree/

## 题目描述

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

 

例如，二叉树 [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
 

进阶：

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


```

## 公司

- 阿里
- 腾讯
- 百度
- 字节
- bloomberg
- linkedin
- microsoft

## 前置知识

- [二叉树](https://github.com/azl397985856/leetcode/blob/master/thinkings/basic-data-structure.md)
- [递归](https://github.com/azl397985856/leetcode/blob/master/thinkings/dynamic-programming.md)

## 思路

看到这题的时候，我的第一直觉是 DFS。然后我就想:`如果左子树是镜像，并且右子树也是镜像，是不是就说明整体是镜像？`。经过几秒的思考， 这显然是不对的，不符合题意。

![](https://tva1.sinaimg.cn/large/007S8ZIlly1ghlu96e83wj31200iugme.jpg)

很明显其中左子树中的节点会和右子树中的节点进行比较，我把比较的元素进行了颜色区分，方便大家看。

这里我的想法是：`遍历每一个节点的时候，如果我都可以通过某种方法知道它对应的对称节点是谁，这样的话我直接比较两者是否一致就行了。`

因此想法是两次遍历，第一次遍历的同时将遍历结果存储到哈希表中，然后第二次遍历去哈希表取。这种方法可行，但是需要 N 的空间（N 为节点总数）。我想到如果两者可以同时进行遍历，是不是就省去了哈希表的开销。

![](https://tva1.sinaimg.cn/large/007S8ZIlly1ghlu9a7sy7j31a30u0408.jpg)

如果不明白的话，我举个简单例子：

```
给定一个数组，检查它是否是镜像对称的。例如，数组 [1,2,2,3,2,2,1] 是对称的。
```

如果用哈希表的话大概是：

```py
seen = dict()
for i, num in enumerate(nums):
    seen[i] = num
for i, num in enumerate(nums):
    if  seen[len(nums) - 1 - i] != num:
      return False
return True
```

而同时遍历的话大概是这样的：

```py
l = 0
r = len(nums) - 1

while l < r:
   if nums[l] != nums[r]: return False
   l += 1
   r -= 1
return True

```

> 其实更像本题一点的话应该是从中间分别向两边扩展 😂

## 代码
代码支持：C++, Java, Python3

C++ Code:
```c++
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        return root==NULL?true:recur(root->left, root->right);
    }

    bool recur(TreeNode* l, TreeNode* r)
    {
        if(l == NULL && r==NULL)
        {
            return true;
        }
        // 只存在一个子节点 或者左右不相等 
        if(l==NULL || r==NULL || l->val != r->val)
        {
            return false;
        }

        return recur(l->left, r->right) && recur(l->right, r->left);
    }
};
```


Java Code:
```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root == null)
        {
            return true;
        }
        else{
            return recur(root.left, root.right);
        }
        // return root == null ? true : recur(root.left, root.right);
    }

    public boolean recur(TreeNode l, TreeNode r)
    {
        if(l == null && r==null)
        {
            return true;
        }
        // 只存在一个子节点 或者左右不相等 
        if(l==null || r==null || l.val != r.val)
        {
            return false;
        }

        return recur(l.left, r.right) && recur(l.right, r.left);
    }
}
```

Python3 Code:
```py

class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        def dfs(root1, root2):
            if root1 == root2 == None: return True
            if not root1 or not root2: return False
            if root1.val != root2.val: return False
            return dfs(root1.left, root2.right) and dfs(root1.right, root2.left)
        if not root: return True
        return dfs(root.left, root.right)
```

**复杂度分析**

- 时间复杂度：$O(N)$，其中 N 为节点数。
- 空间复杂度：递归的深度最高为节点数，因此空间复杂度是 $O(N)$，其中 N 为节点数。

大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库：https://github.com/azl397985856/leetcode 。 目前已经 37K star 啦。
大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。
![](https://tva1.sinaimg.cn/large/007S8ZIlly1gfcuzagjalj30p00dwabs.jpg)

![](https://tva1.sinaimg.cn/large/007S8ZIlly1ghlu9b4p9ej30x20iwjtf.jpg)
