leecode 题目572 另一棵树的子树(python)

本文主要是介绍leecode 题目572 另一棵树的子树(python)，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。

二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。

示例 1：

输入：root = [3,4,5,1,2], subRoot = [4,1,2]
输出：true

示例 2：

输入：root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]
输出：false

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def helper(self, root, subRoot):
        if not root and not subRoot:#保证子树的构造相同
            return True
        if not root or not subRoot:
            return False
        # 保证子树值相同
        return root.val == subRoot.val and self.helper(root.left, subRoot.left) and self.helper(root.right, subRoot.right)

    def isSubtree(self, root: TreeNode, subRoot: TreeNode) -> bool:
        if not root:
            return False
        root_set = [root]
        while(root_set):
            n = root_set[0]
            if n.val == subRoot.val:
                if self.helper(n, subRoot):
                    return True
            if n.left:
                root_set.append(n.left)
            if n.right:
                root_set.append(n.right)    
            root_set.pop(0)
        return False

该问题难度在于如何判断两个子树相同
这里参考评论区的答案使用递归法进行对比

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/subtree-of-another-tree

这篇关于leecode 题目572 另一棵树的子树(python)的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！