leetcode101-对称二叉树

原题

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

例如,二叉树 [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)
彭晨涛彭晨涛管理者
上一篇 2020年1月11日
下一篇 2020年1月12日

相关推荐

  • leetcode367-有效的完全平方数

    原题 给定一个正整数 num,编写一个函数,如果 num 是一个完全平方数,则返回 True,否则返回 False。 说明: 不要使用任何内置的库函数,如  sqrt。 示例1: …

    算法 2020年1月5日
    0150
  • leetcode572-另一个树的子树

    原题 给定两个非空二叉树 s 和 t,检验 s 中是否包含和 t 具有相同结构和节点值的子树。s 的一个子树包括 s 的一个节点和这个节点的所有子孙。s 也可以看做它自身的一棵子树…

    算法 2020年5月8日
    0380
  • leetcode1013-将数组分成和相等的三个部分

    原题 给你一个整数数组 A,只有可以将其划分为三个和相等的非空部分时才返回 true,否则返回 false。 形式上,如果可以找出索引 i+1 < j 且满足 (A[0] +…

    算法 2020年3月11日
    0560
  • leetcode17-电话号码的字母组合

    原题 给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。 给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。 示例: 输入: "23" 输出: …

    2020年5月3日
    0130
  • leetcode35-搜索插入位置

    原题 给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。 你可以假设数组中无重复元素。 示例 1: 输入: […

    算法 2020年3月2日
    0130
  • leetcode111-二叉树的最小深度

    原题 给定一个二叉树,找出其最小深度。 最小深度是从根节点到最近叶子节点的最短路径上的节点数量。 说明: 叶子节点是指没有子节点的节点。 示例: 给定二叉树 [3,9,20,nul…

    算法 2020年3月25日
    0220
  • 使用递归函数逆序一个栈

    原题(来源:牛客网) 一个栈依次压入1,2,3,4,5那么从栈顶到栈底分别为5,4,3,2,1。将这个栈转置后,从栈顶到栈底为1,2,3,4,5,也就是实现了栈中元素的逆序,请设计…

    算法 2020年4月19日
    0250
  • leetcode263-丑数

    原题 编写一个程序判断给定的数是否为丑数。 丑数就是只包含质因数 2, 3, 5 的正整数。 示例1: 输入: 6 输出: true 解释: 6 = 2 × 3 示例2: 输入: …

    算法 2020年2月6日
    0120
  • leetcode203-移除链表元素

    原题 删除链表中等于给定值 val 的所有节点。 示例: 输入: 1->2->6->3->4->5->6, val = 6 输出: 1->2->3->4->5 解法 思想 pre指…

    算法 2019年12月16日
    0360
  • leetcode341-扁平化嵌套列表迭代器

    原题 给定一个嵌套的整型列表。设计一个迭代器,使其能够遍历这个整型列表中的所有整数。 列表中的项或者为一个整数,或者是另一个列表。 示例1: 输入: [[1,1],2,[1,1]]…

    算法 2020年1月27日
    050

发表回复

登录后才能评论