# 101. Symmetric Tree 对称二叉树

@TOC

[LeetCode]

Total Accepted: 106639 Total Submissions: 313969 Difficulty: Easy

## # 题目描述

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree [1,2,2,3,4,4,3] is symmetric:

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

But the following [1,2,2,null,3,null,3] is not:

1
/ \
2   2
\   \
3    3

Note:

1. Bonus points if you could solve it both recursively and iteratively.

## # 解题方法

### # DFS

1
/   \
left->  2     2  <-right
/ \   / \
3   4  4  3

1. leftright的值相等的时候，需要判断下一层是否是对称的。
2. 在递归判断下一层的时候的时候，需要判断的是 left.leftright.right这两棵树是不是对称的，以及 left.rightright.left 这两棵树是不是对称的。

Java代码如下：

/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public boolean isSymmetric(TreeNode root) {
return isMirror(root,root);
}

public boolean isMirror(TreeNode left,TreeNode right){
if(left == null && right == null)   return true;
if(left == null || right == null)   return false;
return (left.val == right.val) && isMirror(left.left,right.right) && isMirror(left.right,right.left);
}
}

AC:1ms

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
def isSymmetric(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
if not root: return True
return self.isMirror(root.left, root.right)

def isMirror(self, left, right):
if not left and not right: return True
if not left or not right: return False
return left.val == right.val and self.isMirror(left.left, right.right) and self.isMirror(left.right, right.left)

### # BFS

BFS 使用一个队列，把要判断是否为镜像的节点放在一起。

BFS做法需要把所有的节点都检查完才能确定返回结果True，除非提前遇到不同的节点值而终止返回False

Java代码如下：

/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public boolean isSymmetric(TreeNode root) {
Queue<TreeNode> q = new LinkedList<>();
while(!q.isEmpty()){
TreeNode left=q.poll();
TreeNode right=q.poll();
if(left==null && right==null)   continue;
if(left==null || right==null)   return false;
if(left.val != right.val)   return false;
}
return true;
}

}

AC:3ms

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
def isSymmetric(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
if not root: return True
que = collections.deque()
que.append(root.left)
que.append(root.right)
while que:
left, right = que.popleft(), que.popleft()
if not left and not right:
continue
if not left or not right:
return False
if left.val != right.val:
return False
que.append(left.left)
que.append(right.right)
que.append(left.right)
que.append(right.left)
return True

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
def isSymmetric(self, root: TreeNode) -> bool:
queue = collections.deque()
queue.append((root, root))
while queue:
left, right = queue.popleft()
if not left and not right:
continue
if not left or not right:
return False
if left.val != right.val:
return False
queue.append((left.left, right.right))
queue.append((left.right, right.left))
return True

## # 日期

2016 年 05月 8日 2018 年 11 月 19 日 —— 周一又开始了 2020 年 5 月 31 日 —— 准备组织每日一题的分享