欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

20190503-相同的树

程序员文章站 2022-06-24 14:14:08
相同的树 难度分类 简单 题目描述 给定两个二叉树,编写一个函数来检验它们是否相同。 如果两个树在结构上相同,并且节点具有相同的值,则认为它们是相同的。 示例 1: 输入: 1 1 / \ / \ 2 3 2 3 [1,2,3], [1,2,3] 输出: true 示例 2: 输入: 1 1 / \ ......

相同的树

难度分类

简单

题目描述

给定两个二叉树,编写一个函数来检验它们是否相同。

如果两个树在结构上相同,并且节点具有相同的值,则认为它们是相同的。

示例 1:

输入:       1         1

          / \       / \

         2   3     2   3

 

        [1,2,3],   [1,2,3]

 

输出: true

示例 2:

输入:      1          1

          /           \

         2             2

 

        [1,2],     [1,null,2]

 

输出: false

示例 3:

输入:       1         1

          / \       / \

         2   1     1   2

 

        [1,2,1],   [1,1,2]

 

输出: false

算法

采用层序遍历只要结构或值不相等就返回false,使用递归解该题具体思路如下:

  1. 递归的结束条件:当比较的treenode的值都为none的时候返回true
  2. 递归条件:比较2个treenode的val,当val相等的时候比较2个treenode的左子树和右子树

考点

  1. 递归
  2. and运算

代码

def issametree(p, q):
    if p is none and q is none:
        return true
    else:
        if p and q:
            if p.val == q.val:#判断当前树节点的值是否相等
                return issametree(p.left, q.left) and issametree(p.right, q.right)
            else:
                return false#如果不相等,则返回false
        else:
            return false

 附:非递归代码

def issametree(p,q):
    a = p
    b = q
    while p and q:
        if p.val == q.val:
            p = p.left
            q = q.left
        else:
            return false
    while a and b:
        if p.val == q.val:
            p = p.right
            q = q.right
        else:
            return false
    if p or p or a or b:
        return false
    return true