题目
给定一个二叉树，检查它是否是镜像对称的。
例如，二叉树 [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
进阶：
你可以运用递归和迭代两种方法解决这个问题吗？
解题
比较推荐方法二和方法三
方法一： 广度优先搜索(BFS)(i)
python解法
利用层序遍历的方式，把每层的节点都放入到tmp中，不存在的节点用 None去代替。
如果该层全有结点的逆序和原来相同，那么就是对称的。
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def isSymmetric(self, root: TreeNode) -> bool: if not root: return True queue = [root] while queue: tmp = [] l = len(queue) for _ in range(l): cur = queue.pop(0) left,right = cur.left,cur.right if left: queue.append(left) tmp.append(left.val) else: tmp.append(None) if right: queue.append(right) tmp.append(right.val) else: tmp.append(None) if tmp!=tmp[::-1]: return False return True
c++解法
c++中并不能使用NULL，因为c++中的NULL就是0，如果节点的值也为0就会出错。
class Solution { public: bool isSymmetric(TreeNode* root) { if(!root) return true; queue<TreeNode*> queue; queue.push(root); while(!queue.empty()){ vector<int> tmp; int l= queue.size(); for(int i=0;i<l;i++){ TreeNode* cur=queue.front(); queue.pop(); TreeNode* left=cur->left; TreeNode* right=cur->right; if(left){ queue.push(left); tmp.push_back(left->val); } else tmp.push_back(INT_MAX); if(right){ queue.push(right); tmp.push_back(right->val); } else tmp.push_back(INT_MAX); } vector<int> tmp2(tmp); reverse(tmp2.begin(),tmp2.end()); if(tmp!=tmp2){ return false; } } return true; } };
方法二：递归(DFS)
python解法
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def isSymmetric(self, root: TreeNode) -> bool: if not root: return True def dfs(left,right): if not (left or right): return True if not (left and right): return False if left.val!=right.val: return False return dfs(left.left,right.right) and dfs(left.right,right.left) return dfs(root.left,root.right)
c++解法
class Solution { public: bool dfs(TreeNode* left,TreeNode* right){ if(!(left||right)) return true; if(!(left&&right)) return false; if(left->val!=right->val) return false; return dfs(left->left,right->right)&&dfs(left->right,right->left); } bool isSymmetric(TreeNode* root) { if(!root) return true; return dfs(root->left,root->right); } };
java解法
class Solution { boolean dfs(TreeNode L,TreeNode R){ if(L==null&&R==null) return true; if(L==null||R==null) return false; if(L.val!=R.val) return false; return dfs(L.left,R.right)&&dfs(L.right,R.left); } public boolean isSymmetric(TreeNode root) { if(root==null) return true; return dfs(root.left,root.right); } }
方法三：迭代(DFS)
这种写法，直接在queue中放入root.left,root.right,是因为判断对称，不用考虑头节点
python解法
class Solution(object): def isSymmetric(self, root): """ :type root: TreeNode :rtype: bool """ if not root or not (root.left or root.right): return True # 用队列保存节点 queue = [root.left,root.right] while queue: # 从队列中取出两个节点，再比较这两个节点 left = queue.pop(0) right = queue.pop(0) # 如果两个节点都为空就继续循环，两者有一个为空就返回false if not (left or right): continue if not (left and right): return False if left.val!=right.val: return False # 将左节点的左孩子， 右节点的右孩子放入队列 queue.append(left.left) queue.append(right.right) # 将左节点的右孩子，右节点的左孩子放入队列 queue.append(left.right) queue.append(right.left) return True
c++解法
class Solution { public: bool isSymmetric(TreeNode* root) { if(!root) return true; queue<TreeNode*> queue; queue.push(root->left); queue.push(root->right); while(!queue.empty()){ TreeNode* left=queue.front(); queue.pop(); TreeNode* right=queue.front(); queue.pop(); if(!(left||right)) continue; if(!(left&&right)) return false; if(left->val!=right->val) return false; queue.push(left->left); queue.push(right->right); queue.push(left->right); queue.push(right->left); } return true; } };
