JZ26 树的子结构

JZ26 树的子结构 ☆☆☆

描述

输入两棵二叉树A,B,判断B是不是A的子结构。(我们约定空树不是任意一个树的子结构)

假如给定A为{8,8,7,9,2,#,#,#,#,4,7},B为{8,9,2},2个树的结构如下,可以看出B是A的子结构

JZ26 树的子结构

数据范围:

0 <= A的节点个数 <= 10000

0 <= B的节点个数 <= 10000

示例1

输入:{8,8,7,9,2,#,#,#,#,4,7},{8,9,2}
返回值:true

示例2

输入:{1,2,3,4,5},{2,4}
返回值:true

示例3

输入:{1,2,3},{3,1}
返回值:false

思路:

hasSubtree(A,B):isSubtree(A,B)or A的左子树 or A的右子树

isSubtree(A,B):根值相同,A左子树包含B左子树,A右子树包含A右子树

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
class Solution:
    def HasSubtree(self , pRoot1: TreeNode, pRoot2: TreeNode) -> bool:
        if not pRoot1 or not pRoot2: return False
        return self.isSub(pRoot1, pRoot2) or self.HasSubtree(pRoot1.left, pRoot2) or self.HasSubtree(pRoot1.right, pRoot2)
    def isSub(self, p1, p2):
        if not p2: return True
        if not p1: return False
        return p1.val==p2.val and self.isSub(p1.left, p2.left) and self.isSub(p1.right, p2.right)
上一篇:C语言程序设计实验报告——实验八


下一篇:小迪day2-基础入门-数据包扩展