题解 | 2023_树的子结构_1446.txt

from collections import deque
from sys import setrecursionlimit

setrecursionlimit(2000)


class TreeNode:
    def __init__(self, val='0', left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def build_tree(nums):
    root = TreeNode(nums[0])
    queue = deque([root])
    i = 1
    while queue and i < len(nums):
        node = queue.popleft()
        if nums[i] != 'null':
            node.left = TreeNode(nums[i])
            queue.append(node.left)
        i += 1
        if i < len(nums) and nums[i] != 'null':
            node.right = TreeNode(nums[i])
            queue.append(node.right)
        i += 1
    return root


def is_match(node1, node2):
    if not node2: return True
    if not node1: return False
    return node1.val == node2.val and is_match(node1.left, node2.left) and is_match(node1.right,
                                                                                    node2.right)


def is_substructure(root1, root2):
    if not root1 or not root2: return False
    return is_match(root1, root2) or is_substructure(root1.left, root2) or is_substructure(root1.right, root2)


if __name__ == '__main__':
    nums1, nums2 = input().split(), input().split()
    root1, root2 = build_tree(nums1), build_tree(nums2)
    print('true' if is_substructure(root1, root2) else 'false')