原题
给定一个二叉树,检查它是否是镜像对称的。
例如,二叉树 [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
说明:
如果你可以运用递归和迭代两种方法解决这个问题,会很加分。
解法
思想
- 迭代,自顶向下比较对称位置的节点。
- 递归,实际上是模拟迭代,将对称位置的节点前后顺序入队列,每次从队列中取出两个元素进行比较。
代码
递归:
class Solution {
public boolean isSymmetric(TreeNode root) {
if(root == null) return true;
return isSymetricUnit(root.left,root.right);
}
public boolean isSymmetricUnit(TreeNode node1,TreeNode node2){
if(node1 == null && node2 == null) return true;
if(node1 == null || node2 == null) return false;
if(node1.val != node2.val) return false;
return isSymmetricUnit(node1.left,node2.right) && isSymmetricUnit(node1.right,node2.left);
}
}
迭代:
public boolean isSymmetric(TreeNode root) {
Queue<TreeNode> q = new LinkedList<>();
q.add(root);
q.add(root);
while (!q.isEmpty()) {
TreeNode t1 = q.poll();
TreeNode t2 = q.poll();
if (t1 == null && t2 == null) continue;
if (t1 == null || t2 == null) return false;
if (t1.val != t2.val) return false;
q.add(t1.left);
q.add(t2.right);
q.add(t1.right);
q.add(t2.left);
}
return true;
}
原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode101-%e5%af%b9%e7%a7%b0%e4%ba%8c%e5%8f%89%e6%a0%91/