[Leetcode] 0572. Subtree of Another Tree

/ Leetcode, 技术文章 / 作者：

Explore diverse LeetCode solutions in Python, C++, JavaScript, SQL, and TypeScript. Ideal for interview prep, learning, and code practice in multiple programming languages. Github Repo Link

内容目录

Easy

Given the roots of two binary trees root and subRoot, return true if there is a subtree of root with the same structure and node values of subRoot and false otherwise.

A subtree of a binary tree tree is a tree that consists of a node in tree and all of this node's descendants. The tree tree could also be considered as a subtree of itself.

 

Example 1:

Input: root = [3,4,5,1,2], subRoot = [4,1,2]
Output: true

Example 2:

Input: root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]
Output: false

 

Constraints:

  • The number of nodes in the root tree is in the range [1, 2000].
  • The number of nodes in the subRoot tree is in the range [1, 1000].
  • -10 4 <= root.val <= 10 4
  • -10 4 <= subRoot.val <= 10 4

Python

				
					# time complexity: O(m*n) # space complexity: O(m+n) from typing import Optional class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right class Solution: def isSameTree(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool: if not root1 and not root2: return True if not root1 or not root2: return False if root1.val != root2.val: return False return self.isSameTree(root1.left, root2.left) and self.isSameTree(root1.right, root2.right) def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool: def dfs(node): if node is None: return False elif self.isSameTree(node, subRoot): return True return dfs(node.left) or dfs(node.right) return dfs(root) root = TreeNode(3) root.left = TreeNode(4) root.left.left = TreeNode(1) root.left.right = TreeNode(2) root.right = TreeNode(5) subRoot = TreeNode(4) subRoot.left = TreeNode(1) subRoot.right = TreeNode(2) print(Solution().isSubtree(root, subRoot))

相关文章