本文共 4076 字，大约阅读时间需要 13 分钟。
给定一个二叉树，检查它是否是镜像对称的。
例如，二叉树 [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
说明:
如果你可以运用递归和迭代两种方法解决这个问题，会很加分。
解法一：递归
# Definition for a binary tree node.# class TreeNode(object):# def __init__(self, x):# self.val = x# self.left = None# self.right = Noneclass 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, p, q): # 判断两棵树是否是镜像树 if not p and not q: # 根节点都为空，是 return True if not p or not q: # 其中有一棵为空，不是 return False l = self.isMirror(p.left, q.right) # p的左子树和q的右子树是否相同 r = self.isMirror(p.right, q.left) # p的右子树和q的左子树是否相同 return p.val == q.val and l and r # 值相等，并且p的左=q的右，p的右=q的左
解法二：使用队列
class Solution: def isSymmetric(self, root): """ 队列 :param root: :return: """ if not root: return True node_queue = [root.left, root.right] # 在空队列中加入左子树和右子树 while node_queue: left = node_queue.pop(0) # 依次弹出两个元素 right = node_queue.pop(0) if not right and not left: # 如果均为空，继续下一个循环 continue if not right or not left: # 如果只有一个为空，返回False return False if left.val != right.val: # 都非空，再判断值是否相等 return False node_queue.append(left.left) # 将两个左右子树的左右子树逆序加入队列 node_queue.append(right.right) node_queue.append(left.right) node_queue.append(right.left) #node_queue.extend([left.left, right.right, left.right, right.left]) 或者用这一句话写 return True
以下是Java版本：
最简单的思路就是先从左子树然后右子树遍历，记录遍历结果，然后再右子树左子树遍历，记录遍历结果，然后对比
两个遍历结果，看是否相等。
1. public class Solution { 2. public boolean isSymmetric(TreeNode root) { 3. if(root == null) 4. return true; 5. StringBuilder builderOfLeft = new StringBuilder(); 6. StringBuilder builderOfRight = new StringBuilder(); 7. String traverseLeft = traverseLeft(root,builderOfLeft); 8. String traverseRight = traverseRight(root,builderOfRight); 9. if(traverseLeft.equals(traverseRight)){ 10. return true; 11. } 12. return false; 13. } 14. public static String traverseLeft(TreeNode root,StringBuilder builder){ 15. if(root == null){ 16. builder.append("null"); 17. return null; 18. } 19. builder.append(root.val+""); 20. traverseLeft(root.left,builder); 21. traverseLeft(root.right,builder); 22. return builder.toString(); 23. } 24. public static String traverseRight(TreeNode root,StringBuilder builder){ 25. if(root == null){ 26. builder.append("null"); 27. return null; 28. } 29. builder.append(root.val+""); 30. traverseRight(root.right,builder); 31. traverseRight(root.left,builder); 32. return builder.toString(); 33. } 34. } 用递归：
1. public class Solution { 2. public boolean isSymmetric(TreeNode root) { 3. if (root == null) { 4. return true; 5. } 6. return isSymmetric(root.left, root.right); 7. } 8. 9. public boolean isSymmetric(TreeNode left, TreeNode right) { 10. if (left == null && right == null) { 11. return true; 12. } 13. 14. if (left == null || right == null) { 15. return false; 16. } 17. 18. return left.val == right.val && isSymmetric(left.left, right.right) && isSymmetric(left.right, right.left); 19. } 20. }
转载地址：http://ypuvi.baihongyu.com/