# 0101. 对称二叉树
### 题目地址(101. 对称二叉树)
### 题目描述
```
给定一个二叉树，检查它是否是镜像对称的。
例如，二叉树 [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
### 前置知识
* [二叉树](/leetcode-solution/thinkings/basic-data-structure.md)
* [递归](/leetcode-solution/thinkings/dynamic-programming.md)
### 思路
看到这题的时候，我的第一直觉是 DFS。然后我就想:`如果左子树是镜像，并且右子树也是镜像，是不是就说明整体是镜像？`。经过几秒的思考， 这显然是不对的，不符合题意。
很明显其中左子树中的节点会和右子树中的节点进行比较，我把比较的元素进行了颜色区分，方便大家看。
这里我的想法是：`遍历每一个节点的时候，如果我都可以通过某种方法知道它对应的对称节点是谁，这样的话我直接比较两者是否一致就行了。`
因此想法是两次遍历，第一次遍历的同时将遍历结果存储到哈希表中，然后第二次遍历去哈希表取。这种方法可行，但是需要 N 的空间（N 为节点总数）。我想到如果两者可以同时进行遍历，是不是就省去了哈希表的开销。
如果不明白的话，我举个简单例子：
```
给定一个数组，检查它是否是镜像对称的。例如，数组 [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:
```
/**
* 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 题解仓库： 。 目前已经 37K star 啦。 大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。 
---
# Agent Instructions: Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/easy/101.symmetric-tree.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.