1. 代码段小站首页
  2. 算法

leetcode101-对称二叉树

彭晨涛 • • 算法 • 阅读 11

原题

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

例如，二叉树 [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. 递归，实际上是模拟迭代，将对称位置的节点前后顺序入队列，每次从队列中取出两个元素进行比较。

代码

递归：

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/

赞 (0)
彭晨涛彭晨涛管理者
0 0
上一篇 2020年1月11日 17:15
下一篇 2020年1月12日 00:07

相关推荐

发表回复

登录后才能评论