leetcode 101. 对称二叉树(迭代和递归)
给定一个二叉树，检查它是否是镜像对称的。
例如，二叉树 [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
进阶：
你可以运用递归和迭代两种方法解决这个问题吗？
题解：
1.二叉树
2.左右元素是否对称
解题思路：
-
迭代实现：参考102. 二叉树的层序遍历
-
注意这里实现第一次把根放入队列两次，当然也可以放入vector再单独编写一个检查是否是回文数组的函数，这里直接从队列中取也可以实现
C/C++题解：
/*** Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };*/
class Solution {
public:
bool isSymmetric(TreeNode* root) {
return ismirror(root,root);}
bool ismirror(TreeNode* p,TreeNode* q){
queue <TreeNode*> Q;//用一个队列来放每一层元素
Q.push(p); Q.push(q);//根节点放入两次
while (!Q.empty()) {
p = Q.front(); Q.pop();
q = Q.front(); Q.pop();
if (!p && !q) continue;//根的左右子树节点数或值不对称
if ((!p || !q) || (p->val != q->val)) return false;
Q.push(p->left); //把p,q的子节点都放入队列
Q.push(q->right);
Q.push(p->right); //注意顺序体现对称位置
Q.push(q->left);}
return true;}};
class Solution {
public:
bool isSymmetric(TreeNode* root) {
return ismirror(root,root);}
bool ismirror(TreeNode* p,TreeNode* q){
if(!p&&!q)//都为空树，对称 return true;
if(!p||!q)//有一个为空，则不对称 return false;
if(p->val==q->val) //检查节点值，并递归对应位置
return ismirror(p->left,q->right)&&ismirror(p->right,q->left);
return false; }}; //节点值不等，不对称
Debug结果：
Java题解：
/*** Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }*/
class Solution {
public boolean isSymmetric(TreeNode root) {
return ismirror(root,root); }
public boolean ismirror(TreeNode p,TreeNode q){
Queue <TreeNode> Q = new LinkedList<TreeNode>();//用一个队列来放每一层元素
Q.offer(p); Q.offer(q);//根节点放入两次
while (!Q.isEmpty()) {
p = Q.poll();
q = Q.poll();
if (p == null && q == null) continue;//根的左右子树节点数或值不对称
if ((p==null || q==null) || (p.val != q.val)) return false;
Q.offer(p.left); //把p,q的子节点都放入队列
Q.offer(q.right);
Q.offer(p.right); //注意顺序体现对称
Q.offer(q.left);}
return true;}}
class Solution {
public boolean isSymmetric(TreeNode root) {
return ismirror(root,root);}
public boolean ismirror(TreeNode p,TreeNode q){
if(p == null && q == null)//都为空树，对称
return true;
if(p == null ||q == null)//有一个为空，则不对称
return false;
if(p.val==q.val) //检查节点值，并递归对应位置
return ismirror(p.left,q.right)&&ismirror(p.right,q.left);
return false; }} //节点值不等，不对称
Debug结果：
Python题解：
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def isSymmetric(self, root):
""":type root: TreeNode:rtype: bool"""
def ismirror(p, q):
Q = []#用一个队列来放每一层元素
Q.append(p); Q.append(q)#根节点放入两次
while Q:
p = Q.pop(0)
q = Q.pop(0)
if not p and not q: continue #根的左右子树节点数或值不对称
if ((not p or not q) or (p.val != q.val)): return False
Q.append(p.left) #把p,q的子节点都放入队列
Q.append(q.right)
Q.append(p.right) #注意顺序体现对称
Q.append(q.left)
return True
return ismirror(root, root)
class Solution(object):
def isSymmetric(self, root):
""":type root: TreeNode:rtype: bool"""
def ismirror(p, q):
if not p and not q: #都为空树，对称
return True
if not p or not q:#有一个为空，则不对称
return False
if p.val==q.val: #检查节点值，并递归对应位置
return ismirror(p.left,q.right) and ismirror(p.right,q.left)
return False #节点值不等，不对称
return ismirror(root, root)
Debug结果：
更多题解移步公众号免费获取