. 등가 이진 트리 뒤집기

951. 등가 이진 트리 뒤집기

난이도:중

주제: 트리, 깊이 우선 탐색, 이진 트리

이진 트리T의 경우 다음과 같이 반전 작업을 정의할 수 있습니다. 임의의 노드를 선택하고 왼쪽 및 오른쪽 하위 트리를 교환합니다.

이진 트리 X는 X를 X와 같게 만들 수 있는 경우에만 이진 트리 Y와 뒤집기 등가입니다. 🎜>Y

몇 번의 뒤집기 작업 후.

두 이진 트리 root1과 root2의 루트가 주어지면 두 트리가 뒤집힌 동등이면 true를 반환하고, 그렇지 않으면 false

를 반환합니다.

예 1:

• 입력:
root1 = [1,2,3,4,5,6,null,null,null,7,8], root2 = [1,3,2,null,6,4,5 ,null,null,null,null,8,7]
• 출력:
true
• 설명:
값이 1, 3, 5인 노드를 뒤집었습니다.

예 2:

• 입력:
root1 = [], root2 = []
• 출력:
true

예 3:

• 입력:
root1 = [], root2 = [1]
• 출력:
false

제약조건:

각 트리의 노드 수는 [0, 100] 범위에 있습니다.
각 트리는 [0, 99] 범위의 고유한 노드 값을 갖습니다.

해결책:

재귀적 깊이 우선 검색(DFS)을 사용할 수 있습니다. 아이디어는 루트 값이 동일하고 하위 트리가 동일하거나(플립 없이) 일부 노드에서 왼쪽 및 오른쪽 하위 트리를 뒤집은 후 동일하게 되는 경우 두 트리가 대칭 뒤집기 등가라는 것입니다.

계획:

1. 기본 사례:

   root1과 root2가 모두 null이면 간단히 뒤집기 동일합니다.
   그 중 하나만 null이면 동일할 수 없습니다.
   root1과 root2의 루트 값이 다르면 동일할 수 없습니다.

2. 재귀적 사례:

   • 두 가지 가능성을 재귀적으로 확인합니다.
     root1의 왼쪽 하위 트리는 root2의 왼쪽 하위 트리와 동일한 반전이고, root1의 오른쪽 하위 트리는 root2의 오른쪽 하위 트리와 동일한 반전입니다(즉, 반전 없음).
     root1의 왼쪽 하위 트리는 root2의 오른쪽 하위 트리와 동일한 반전이고, root1의 오른쪽 하위 트리는 root2의 왼쪽 하위 트리와 동일한 반전입니다(즉, 자식 반전).

이 솔루션을 PHP로 구현해 보겠습니다: 951. 등가 이진 트리 뒤집기

<?php
// Definition for a binary tree node.
class TreeNode {
    public $val;
    public $left;
    public $right;
    function __construct($val = 0, $left = null, $right = null) {
        $this->val = $val;
        $this->left = $left;
        $this->right = $right;
    }
}

/**
 * @param TreeNode $root1
 * @param TreeNode $root2
 * @return Boolean
 */
function flipEquiv($root1, $root2) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage:
$root1 = new TreeNode(1,
    new TreeNode(2, new TreeNode(4), new TreeNode(5, new TreeNode(7), new TreeNode(8))),
    new TreeNode(3, new TreeNode(6), null)
);

$root2 = new TreeNode(1,
    new TreeNode(3, null, new TreeNode(6)),
    new TreeNode(2, new TreeNode(4), new TreeNode(5, new TreeNode(8), new TreeNode(7)))
);

var_dump(flipEquiv($root1, $root2)); // Output: bool(true)
?>

설명:

1. TreeNode 클래스: TreeNode 클래스는 노드 값, 왼쪽 자식 및 오른쪽 자식을 초기화하는 생성자를 사용하여 이진 트리의 노드를 나타냅니다.

2. flipEquiv 기능:

   • 기본 사례는 두 노드가 모두 null이거나, 하나가 null이거나, 값이 일치하지 않는 경우를 처리합니다.
   • 재귀 사례는 두 가지 가능성(비반전 또는 반전)을 모두 확인하여 두 조건 모두에서 하위 트리가 반전되는지 확인합니다.

시간 복잡도:

• 이 함수는 두 트리의 모든 노드를 확인하며 각 재귀 호출은 두 개의 하위 트리를 처리합니다. 따라서 시간 복잡도는 O(N)입니다. 여기서 N은 트리의 노드 수입니다.

공간 복잡도:

• 공간 복잡도는 O(H)입니다. 여기서 H는 재귀 스택으로 인해 트리의 높이입니다. 최악의 경우(비뚤어진 트리의 경우) O(N)이 될 수 있습니다.

연락처 링크

이 시리즈가 도움이 되었다면 GitHub에서 저장소에 별표를 표시하거나 즐겨찾는 소셜 네트워크에서 게시물을 공유해 보세요. 여러분의 지원은 저에게 큰 의미가 될 것입니다!

이런 유용한 콘텐츠를 더 원하시면 저를 팔로우해주세요.

• 링크드인
• 깃허브

위 내용은 . 등가 이진 트리 뒤집기의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!