leetcode: 100. Same Tree

Problem

# Given two binary trees, write a function to check if they are the same or not.
#
# Two binary trees are considered the same if they are structurally identical 
# and the nodes have the same value.
#
#
# Example 1:
#
# Input:
#       1         1
#      / \       / \
#     2   3     2   3
#
#   [1,2,3],   [1,2,3]
#
# Output: true
# Example 2:
#
# Input:
#       1         1
#      /           \
#     2             2
#
#   [1,2],     [1,null,2]
#
# Output: false
# Example 3:
#
# Input:
#       1         1
#      / \       / \
#     2   1     1   2
#
#   [1,2,1],   [1,1,2]
#
# Output: false

Idea

对两棵树的每个相同位置都进行比较。一旦某结点不一致,即返False。

判断顺序:
1. not node1 and not node2:    continue
2. None in (node1, node2) 或 node1.val != node2.val:    返False
3. node1.val == node2.val:    继续判断左右子树

AC

栈:

# Time:  O(n)
# Space: O(h)
class Solution():
    def isSameTree(self, p, q):
        stack = [(p, q)]
        while stack:
            node1, node2 = stack.pop()
            if not node1 and not node2:
                continue
            if None in (node1, node2) or node1.val != node2.val:
                return False
            else:
                stack.append((node1.left, node2.left))
                stack.append((node1.right, node2.right))
        return True

递归:

# Time:  O(n)
# Space: O(h)
class Solution():
    def isSameTree(self, p, q):
        if not p and not q:
            return True
        if None in (p, q) or p.val != q.val:
            return False
        else:
            return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏于晓飞的专栏

读 Java Arrays 源码 笔记

Arrays.java是Java中用来操作数组的类。使用这个工具类可以减少平常很多的工作量。了解其实现,可以避免一些错误的用法。

972
来自专栏好好学java的技术栈

自己动手写一个单链表

单向链表(单链表)是链表的一种,其特点是链表的链接方向是单向的,对链表的访问要通过顺序读取从头部开始。

2386
来自专栏工科狗和生物喵

【计算机本科补全计划】Java学习笔记(九) Java日期时间

### 1、 Java 日期时间 java.util 包提供了 Date 类来封装当前的日期和时间。 Date 类提供两个构造函数来实例化 Date 对象。第一...

932
来自专栏java一日一条

如何用Map对象创建Set对象

Java中的Map和Set有不少相似之处。本文将分享一个把Map类转化成Set类的小技巧。

821
来自专栏拭心的安卓进阶之路

Java 集合源码解析(1):Iterator

Java, Android 开发也有段时间了,当初为了早点学 Android,Java 匆匆了解个大概就结束了,基础不够扎实。 虽然集合框架经常用,但是一直...

2245
来自专栏Android开发小工

Java集合解惑

本文取自工匠若水的qq群里的Java基础题目,把里面有关Java集合放在一起。 全文github地址

1192
来自专栏来自地球男人的部落格

[LeetCode] 347. Top K Frequent Elements

【原题】 Given a non-empty array of integers, return the k most frequent elements...

2857
来自专栏java工会

java集合详解

24210
来自专栏一枝花算不算浪漫

Java中常见数据结构Map之LinkedHashMap

3213
来自专栏互扯程序

Java常用集合源码级深度解析

Java集合工具包位于Java.util包下,包含了很多常用的数据结构,如数组、链表、栈、队列、集合、哈希表等。学习Java集合框架下大致可以分为如下五个部分:...

5006

扫码关注云+社区

领取腾讯云代金券