给定一个二叉树,检查它是否是镜像对称的。
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
本文分享自微信公众号 - 爱写Bug(iCodeBugs),作者:爱写Bug
原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。
原始发表时间:2020-02-10
本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。
我来说两句