给定一个二叉树,检查它是否是镜像对称的。
Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).
例如,二叉树 [1,2,2,3,4,4,3]
是对称的。
For example, this binary tree [1,2,2,3,4,4,3]
is symmetric:
1
/ \
2 2
/ \ / \
3 4 4 3
但是下面这个 [1,2,2,null,3,null,3]
则不是镜像对称的:
But the following [1,2,2,null,3,null,3]
is not:
1
/ \
2 2
\ \
3 3
说明:
如果你可以运用递归和迭代两种方法解决这个问题,会很加分。
Note: Bonus points if you could solve it both recursively and iteratively.
很简单的题, 深度优先的话同时遍历二叉树的左右子结点稍加判断即可; 广度优先的话, 一次按镜像对称从两边遍历二叉树, 一次同时取出来两个结点稍加判断即可. 这里列举两种最好的解法, 复杂度相同
Java:
class Solution {
public boolean isSymmetric(TreeNode root) {
if (root == null) // 根结点为空直接返回 真
return true;
return isSymmetricHelper(root.left, root.right); // 辅助函数传入根结点的左右子结点
}
private boolean isSymmetricHelper(TreeNode node1, TreeNode node2) {
if (node1 == null && node2 == null) // 两结点均为空时也满足镜像对称的条件, 返回为真
return true;
if (node1 == null || node2 == null) // 两结点只有一个为空, 则不满足对称条件, 返回值为假
return false;
// 当两结点值相等, 所有子结点均满足对称条件时, 返回为真, 否则返回为假
return (node1.val == node2.val) && isSymmetricHelper(node1.left, node2.right) && isSymmetricHelper(node1.right, node2.left);
}
}
Python:
class Solution:
def isSymmetric(self, root: TreeNode) -> bool:
if not root: # 根结点为空直接返回 真
return True
return self.isSymmetricHelper(root.left, root.right) # 辅助函数传入根结点的左右子结点
def isSymmetricHelper(self, node1: TreeNode, node2: TreeNode) -> bool:
if not node1 and not node2: # 两结点均为空时也满足镜像对称的条件, 返回为真
return True
if not node1 or not node2: # 两结点只有一个为空, 则不满足对称条件, 返回值为假
return False
# 当两结点值相等, 所有子结点均满足对称条件时, 返回为真, 否则返回为假
return node1.val == node2.val and self.isSymmetricHelper(node1.left, node2.right) and self.isSymmetricHelper(node1.right, node2.left)
Java:
class Solution {
public boolean isSymmetric(TreeNode root) {
if (root == null) // 根结点为空直接返回 真
return true;
Queue<TreeNode> queue = new LinkedList<>(); // 维护一个队列, 从左右子结点同时入队维护
queue.add(root.left);
queue.add(root.right);
int size;
TreeNode node1, node2;
while (!queue.isEmpty()) {
node1 = queue.poll();
node2 = queue.poll();
if (node1 == null && node2 == null) // 两结点均为空时也满足镜像对称的条件, 跳过该层循环
continue;
if (node1 == null || node2 == null) // 两结点只有一个为空, 则不满足对称条件, 返回值为假
return false;
if (node1.val != node2.val) // 两结点值不相等时, 返回为假
return false;
// 按镜像对称条件, 依次入队
queue.add(node1.left);
queue.add(node2.right);
queue.add(node1.right);
queue.add(node2.left);
}
return true;
}
}
Python:
class Solution:
def isSymmetric(self, root):
if not root: # 根结点为空直接返回 真
return True
queue = collections.deque() # 维护一个队列, 从左右子结点同时入队维护
queue.append(root.left)
queue.append(root.right)
while queue:
node1 = queue.popleft()
node2 = queue.popleft()
if node1 == None and node2 == None: # 两结点均为空时也满足镜像对称的条件, 跳过该层循环
continue
if node1 == None or node2 == None: # 两结点只有一个为空, 则不满足对称条件, 返回值为假
return False
if node1.val != node2.val: # 两结点值不相等时, 返回为假
return False
# 按镜像对称条件, 依次入队
queue.append(node1.left)
queue.append(node2.right)
queue.append(node1.right)
queue.append(node2.left)
return True