20190503-相同的树

相同的树

难度分类

简单

题目描述

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

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

示例 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

原文链接:https://www.cnblogs.com/hyj691001/p/10806343.html
如有疑问请与原作者联系

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有