What is the best way to solve Subtree of Another Tree?

The optimized O(1) approach using Trees patterns is generally preferred.

상위 150개 인터뷰중간

다른 트리의 하위 트리

'다른 트리의 하위 트리' 문제에 대한 자세한 가이드 및 Python 구현입니다.

문제 설명

중간

두 이진 트리 root와 subRoot의 루트가 주어지면 subRoot의 구조와 노드 값이 동일한 루트의 하위 트리가 있으면 true를 반환하고 그렇지 않으면 false를 반환합니다.

이진 트리 트리의 하위 트리는 트리의 노드와 이 노드의 모든 자손으로 구성된 트리입니다. 트리 트리는 그 자체의 하위 트리로 간주될 수도 있습니다.

트리는 레벨 순서 목록으로 표시됩니다. isSubtree(root: list, subRoot: list) -> bool 함수를 구현하세요.

제약

•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]
•-10000 <= root.val <= 10000
•-10000 <= subRoot.val <= 10000

예

Example 1

Input

[3,4,5,1,2], [4,1,2]

Output

True

Explanation

The subtree rooted at node 4 in the main tree matches subRoot exactly.

Example 2

Input

[3,4,5,1,2,None,None,None,None,0], [4,1,2]

Output

False

Explanation

The subtree rooted at 4 in the main tree has an extra node 0 under 2, so it doesn't match subRoot.

Need a Hint?

세트나 힙과 같은 트리 관련 데이터 구조를 사용해 보세요.

Edge Cases to Watch

빈 입력 구조
단일 요소 입력
큰 수치 범위

해결할 준비가 되셨나요?

Open the problem in PyRun's browser-based Python editor. Your code runs fully offline — no server required.

편집기에서 열기

인터뷰 통찰력 및 변형

Trees 접근 방식의 논리를 설명하세요.

null 또는 빈 입력과 같은 극단적인 경우에 대해 논의합니다.

복잡성 분석 분석

무차별 대입 복잡성

Time: O(n)•Space: O(1)

왜 시간인가?: Directly evaluates all possibilities.

왜 우주인가?: Uses standard local memory.

최적화된 복잡성

Time: O(1)•Space: O(1)

왜 시간인가?: Optimized paths reduce total operations.

왜 우주인가?: May trade memory for speed.

최적화된 솔루션 Python 코드

컴파일러에서 시도해 보세요

def is_subtree_opt(root, subRoot):
    if isinstance(root, list):
        r1 = build_tree(root)
        r2 = build_tree(subRoot)
        return is_subtree_opt_helper(r1, r2)
    return is_subtree_opt_helper(root, subRoot)

def is_subtree_opt_helper(root: TreeNode, subRoot: TreeNode) -> bool:
    def is_same(p, q):
        if not p and not q:
            return True
        if not p or not q or p.val != q.val:
            return False
        return is_same(p.left, q.left) and is_same(p.right, q.right)
    if not subRoot: return True
    if not root: return False
    if is_same(root, subRoot): return True
    return is_subtree_opt_helper(root.left, subRoot) or is_subtree_opt_helper(root.right, subRoot)

무차별 대입 코드(스포일러 보호)

컴파일러에서 시도해 보세요

def is_subtree_brute(root, subRoot):
    if isinstance(root, list):
        r1 = build_tree(root)
        r2 = build_tree(subRoot)
        return is_subtree_brute_helper(r1, r2)
    return is_subtree_brute_helper(root, subRoot)

def is_subtree_brute_helper(root: TreeNode, subRoot: TreeNode) -> bool:
    def same(p, q):
        if not p and not q: return True
        if not p or not q or p.val != q.val: return False
        return same(p.left, q.left) and same(p.right, q.right)
    if not root: return False
    if same(root, subRoot): return True
    return is_subtree_brute_helper(root.left, subRoot) or is_subtree_brute_helper(root.right, subRoot)