バイナリツリーが他のバイナリツリーのサブツリーであるかどうかを調べる

木の子孫であるすべては、subtreeとして知られています.
sがsの子孫であるならば、2進木(s)はもう一つの二分木(t)の下位木であると言われています、そして、sのように正確な順序に従ってください.

    7
   / \
  4   8
 / \
3  6

上記の木のために

   4                   |           4                                
  / \                  |          / 
 3   6                 |         3
                       |
This is a subtree      |       This is not a subtree
                       |        

場合は、解決策をチェックする前に、この問題を解決する好奇心旺盛です.Leetcodeで試してみてください😉 .
あなたはhttps://github.com/harsha-sam/Leetcode-Solutionsで他のleetcode問題に私の解決策を見つけることができます.

解決策
leetcodeからBoilerplateコードを使用します.直接ソリューションを提出することができますし、確認すると、一度アルゴリズムをどのように動作を理解します.
ノードの比較

深さ優先探索ツリーツリーとツリーツリーのルートノードと同じ値を持つノードを見つけるたびに、Tのこの対応するノードからツリーTとSの両方を比較し、両方のツリーのすべてのノードを比較することによって、等値を確認します.

# 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 isSubtree(self, s: TreeNode, t: TreeNode) -> bool:
        '''
        Depth first searches both trees and compares 
        all nodes. 
        Returns False whenever two different nodes 
        encountered
        Returns True when both trees are completely 
        explored and equal.
        '''
        def check_equal(tree1, tree2):
            if tree1 and not tree2 or tree2 and not tree1:
                return False
            elif tree1 and tree2:
                if tree1.val != tree2.val:
                    return False
                if not check_equal(tree1.left, tree2.left):
                    return False
                if not check_equal(tree1.right, tree2.right):
                    return False
            return True

        def explore(curr, t):
            if curr:
                # if a node which has same value as root s is encountered, we check for quality
                if curr.val == t.val and check_equal(curr, t):
                    return True
                if explore(curr.left, t):
                    return True
                if explore(curr.right, t):
                    return True

        return explore(s, t)

Time Complexity: O(N * M) - Where M = number of nodes in subtree t and N = number of nodes in tree sSpace Complexity: O(N) - Depth in recursion can go upto n nodes. n refers to number of nodes in s.