[リートコード] 0572. 別のツリーのサブツリー

/ リートコード, テクニカル記事 / による

Python、C++、JavaScript、SQL、TypeScript の多様な LeetCode ソリューションを探索してください。面接の準備、学習、複数のプログラミング言語でのコードの練習に最適です。 Github リポジトリ リンク

簡単

2つの二分木の根が与えられた場合 根 そして サブルート、 戻る 真実 のサブツリーがある場合 根 同じ構造とノード値を持つ サブルート そして 間違い さもないと。

二分木のサブツリー 木 は、ノードで構成されるツリーです。 木 そしてこのノードのすべての子孫。木 木 それ自体のサブツリーと見なすこともできます。

 

例 1:

入力： ルート = [3,4,5,1,2]、サブルート = [4,1,2]
出力： 真実

例 2:

入力： ルート = [3,4,5,1,2,null,null,null,null,0]、サブルート = [4,1,2]
出力： 間違い

 

制約:

  • ノードの数は 根 木は範囲内にある [1, 2000].
  • ノードの数は サブルート 木は範囲内にある [1, 1000].
  • -10 4 <= ルート値 <= 10 4
  • -10 4 <= サブルート値 <= 10 4

パイソン

				
					#時間計算量: O(m*n) #空間計算量: O(m+n) 入力から OptionalクラスTreeNodeをインポート: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right クラス 解決法: def isSameTree(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool: root1でもroot2でもない場合は: Trueを返す root1でもroot2でもない場合は: Falseを返す root1.val != root2.valの場合は: Falseを返す self.isSameTree(root1.left, root2.left)かつself.isSameTree(root1.right, root2.right)を返す def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool: def dfs(node): ノードがなし: False を返します elif self.isSameTree(node, subRoot): True を返します return dfs(node.left) または 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))

関連記事