另一个树的子树

给定两个非空二叉树 s 和 t,检验 s 中是否包含和 t 具有相同结构和节点值的子树。s 的一个子树包括 s 的一个节点和这个节点的所有子孙。s 也可以看做它自身的一棵子树。

示例 1:
给定的树 s:

3
/ \
4 5
/ \
1 2
给定的树 t:

4
/ \
1 2
返回 true,因为 t 与 s 的一个子树拥有相同的结构和节点值。

示例 2:
给定的树 s:

3
/ \
4 5
/ \
1 2
/
0
给定的树 t:

4
/ \
1 2
返回 false。

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

解题思路:对该树进行递归搜索,需要用到双递归,一个是对树的起始结点的递归,另一个是找到起始结点后进行比较的递归,设置好条件之后就可以开始了。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def isSubtree(self, s: TreeNode, t: TreeNode) -> bool:
        def dfs(root1, root2):
            if not root2: return not root1
            if not root1: return False
            if root1.val != root2.val: return False

            return dfs(root1.left, root2.left) and dfs(root1.right, root2.right)

        if not s: return False
        return dfs(s, t) or self.isSubtree(s.left, t) or self.isSubtree(s.right, t)

 

在评论区看到的一行python代码长见识了。

 

return str(s).find(str(t)) != -1
点赞

发表评论

昵称和uid可以选填一个,填邮箱必填(留言回复后将会发邮件给你)
tips:输入uid可以快速获得你的昵称和头像

Title - Artist
0:00