Subtree of Another Tree

# 問題

二分木root，subRootが与えられる．subRootがrootの部分木であるかを判定せよ．

# 答え

再帰的に解く
- 根から再帰的に値が一致しているかを確認
- isSubtree(root, subRoot): rootを根としてsubRootと重ねる
- is_same(s, t): sを根とする木とtを根とする木が重なるかを確認する
- 計算量
  - rootの頂点数を$s$，subRootの頂点数を$t$とすると，$O(s \times t)$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# 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, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
        def is_same(root1, root2):
            if root1 is None and root2 is None:
                return True
            if root1 is not None and root2 is None:
                return False
            if root1 is None and root2 is not None:
                return False
            return root1.val == root2.val and is_same(root1.left, root2.left) and is_same(root1.right, root2.right)

        if root is None and subRoot is None:
            return True
        if root is not None and subRoot is None:
            return False
        if root is None and subRoot is not None:
            return False
        return is_same(root, subRoot) or self.isSubtree(root.left, subRoot) or self.isSubtree(root.right, subRoot)

上のやりかただと，すべての頂点について重なるかを根の方から調べていく．どんどん木を降りていくと過去に重ねたのと同じものを再度計算することになるのでそれを回避するともうチョット効率が良さそう．

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
# 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, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
        def is_same(root1, root2):
            if root1 is None and root2 is None:
                return True
            if root1 is not None and root2 is None:
                return False
            if root1 is None and root2 is not None:
                return False
            return root1.val == root2.val and is_same(root1.left, root2.left) and is_same(root1.right, root2.right)
        result = False

        def dfs(root):
            nonlocal result
            if result:
                return
            if root is None:
                return
            if root.val == subRoot.val:
                result = is_same(root, subRoot)
            dfs(root.left)
            dfs(root.right)
        dfs(root)
        return result

木構造を文字列にエンコードして部分文字列に含まれるかを調べるやり方
- [12, None, None]と[2, None, None]のようなときに区別できるようにエンコードを注意する．
  - 要するに12-...と2-...が区別できればいいので，-12-...と-2-...みたいに前になにかつけてやればいい

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
# 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, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
        def encode(root):
            if root is None:
                return "#"
            return "-" + str(root.val) + "-" + encode(root.left) + "-" + encode(root.right) + "-"
        return encode(subRoot) in encode(root)

上のエンコードするやり方を繰り返しで書き下すと次のように書ける

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
# 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, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
        def encode(root):
            suspended = [root]
            traversal = []
            while len(suspended) != 0:
                node = suspended.pop()
                if node is None:
                    traversal.append("#")
                    continue
                else:
                    traversal.append(str(node.val))
                    suspended.append(node.left)
                    suspended.append(node.right)
            return "-" + "-".join(traversal) + "-"
        return encode(subRoot) in encode(root)

merkle tree
- 木構造をマークルハッシュでまとめる
- ハッシュ関数が衝突しない限り正解
- やりすぎ
- 計算量
  - rootの頂点数を$s$，subRootの頂点数を$t$とすると，$O(s + t)$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
# 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, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
        from hashlib import sha256
        def _hash(x):
            S = sha256()
            S.update(str.encode(x))
            return S.hexdigest()

        def merkle(node):
            if node is None:
                return ""
            left_merkle = merkle(node.left)
            right_merkle = merkle(node.right)
            node.merkle = _hash(left_merkle + str(node.val) + right_merkle)
            return node.merkle

        merkle(root)
        merkle(subRoot)

        def dfs(node):
            if node is None:
                return False
            return node.merkle == subRoot.merkle or dfs(node.left) or dfs(node.right)

        return dfs(root)

# Ref

https://leetcode.com/problems/subtree-of-another-tree/