LeetCode 101: 对称二叉树 Symmetric Tree

题目：

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

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 Truereturn self.isSymmetricHelper(root.left, root.right) # 辅助函数传入根结点的左右子结点def isSymmetricHelper(self, node1: TreeNode, node2: TreeNode) -> bool:if not node1 and not node2: # 两结点均为空时也满足镜像对称的条件, 返回为真return Trueif 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 Truequeue = collections.deque() # 维护一个队列, 从左右子结点同时入队维护queue.append(root.left)queue.append(root.right)while queue:node1 = queue.popleft()node2 = queue.popleft()if node1 == None and node2 == None: # 两结点均为空时也满足镜像对称的条件, 跳过该层循环continueif node1 == None or node2 == None: # 两结点只有一个为空, 则不满足对称条件, 返回值为假return Falseif node1.val != node2.val: # 两结点值不相等时, 返回为假return False# 按镜像对称条件, 依次入队queue.append(node1.left)queue.append(node2.right)queue.append(node1.right)queue.append(node2.left)return True