题解 | 2023_树的子结构_1446.txt
2023_树的子结构_1446.txt
https://www.nowcoder.com/practice/0c9236ef3e9c4682866fd34214166836
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')
