이진 트리 II의 사촌-PHP 튜토리얼-php.cn

2641. 이진나무의 사촌 II

난이도:중

주제: 해시 테이블, 트리, 깊이 우선 검색, 너비 우선 검색, 이진 트리

이진 트리의 루트가 주어지면 트리의 각 노드 값을 모든 사촌 값의 합으로 바꿉니다.

이진 트리의 두 노드는 서로 다른 부모와 동일한 깊이를 갖는 경우 사촌입니다.

수정된 트리의 루트를 반환합니다.

참고 노드의 깊이는 루트 노드에서 해당 노드까지의 경로에 있는 가장자리의 수입니다.

예 1:

Cousins in Binary Tree II

입력: 루트 = [5,4,9,1,10,null,7]
출력: [0,0,0,7,7,null,11]
설명: 위의 다이어그램은 초기 바이너리 트리와 각 노드의 값을 변경한 후의 바이너리 트리를 보여줍니다.
- 값이 5인 노드에는 사촌이 없으므로 그 합은 0입니다.
- 값이 4인 노드에는 사촌이 없으므로 그 합은 0입니다.
- 값이 9인 노드에는 사촌이 없으므로 그 합은 0입니다.
- 값이 1인 노드에는 값이 7인 사촌이 있으므로 그 합은 7입니다.
- 값이 10인 노드에는 값이 7인 사촌이 있으므로 그 합은 7입니다.
- 값이 7인 노드에는 값이 1과 10인 사촌이 있으므로 그 합은 11입니다.

예 2:

Cousins in Binary Tree II

입력: 루트 = [3,1,2]
출력: [0,0,0]
설명: 위의 다이어그램은 초기 바이너리 트리와 각 노드의 값을 변경한 후의 바이너리 트리를 보여줍니다.
- 값이 3인 노드에는 사촌이 없으므로 그 합은 0입니다.
- 값이 1인 노드에는 사촌이 없으므로 그 합은 0입니다.
- 값이 2인 노드에는 사촌이 없으므로 그 합은 0입니다.

제약조건:

트리의 노드 수는 [1, 10⁵] 범위에 있습니다.
1 <= Node.val <= 10⁴

힌트:

DFS를 두 번 사용하세요.
처음으로 이진 트리의 모든 수준 값의 합을 구합니다.
두 번째로, 현재 레벨의 값인 형제 노드의 값의 합으로 노드의 값을 업데이트합니다.

해결책:

이 솔루션은 깊이 우선 검색(DFS) 접근 방식을 두 번 사용합니다.

첫 번째 DFS: 트리의 각 수준에서 모든 노드 값의 합을 계산합니다.
두 번째 DFS: 해당 레벨의 총계에서 형제의 값을 빼서 각 노드의 값을 사촌의 값의 합으로 업데이트합니다.

이 솔루션을 PHP로 구현해 보겠습니다: 2641. 이진나무의 사촌 II

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

class Solution {

    /**
     * @param TreeNode $root
     * @return TreeNode
     */
    public function replaceValueInTree($root) {
       ...
       ...
       ...
       /**
        * go to ./solution.php
        */
    }

    /**
     * DFS to calculate the sum of node values at each level.
     * @param $root - current node
     * @param $level - current depth level in the tree
     * @param $levelSums - array holding the sum of values at each level
     * @return void
     */
    private function dfs($root, $level, &$levelSums) {
       ...
       ...
       ...
       /**
        * go to ./solution.php
        */
    }

    /**
     * DFS to replace the node values with the sum of cousins' values.
     * @param $root - current node in the original tree
     * @param $level - current depth level in the tree
     * @param $curr - node being modified in the new tree
     * @param $levelSums - array holding the sum of values at each level
     * @return mixed
     */
    private function replace($root, $level, $curr, $levelSums) {
       ...
       ...
       ...
       /**
        * go to ./solution.php
        */
    }
}

// Helper function to print the tree (for testing purpose)
function printTree($root) {
    if ($root === null) return [];

    $result = [];
    $queue = [$root];

    while (!empty($queue)) {
        $node = array_shift($queue);
        if ($node !== null) {
            $result[] = $node->val;
            $queue[] = $node->left;
            $queue[] = $node->right;
        } else {
            $result[] = null;
        }
    }

    // Remove trailing null values for clean output
    while (end($result) === null) {
        array_pop($result);
    }

    return $result;
}

// Example usage:

// Tree: [5,4,9,1,10,null,7]
$root = new TreeNode(5);
$root->left = new TreeNode(4);
$root->right = new TreeNode(9);
$root->left->left = new TreeNode(1);
$root->left->right = new TreeNode(10);
$root->right->right = new TreeNode(7);

$solution = new Solution();
$modifiedTree = $solution->replaceValueInTree($root);

print_r(printTree($modifiedTree));  // Output: [0, 0, 0, 7, 7, null, 11]
?>




<h3>
  
  
  코드 분석
</h3>

<h4>
  
  
  1.replaceValueInTree 메소드
</h4>

<ul>
<li>프로세스를 초기화하는 주요 메소드입니다.</li>
<li>각 수준의 값 합계를 보관하기 위해 빈 배열 $levelSums를 생성합니다.</li>
<li>첫 번째 DFS를 호출하여 $levelSums를 채운 다음 두 번째 DFS를 호출하여 트리의 값을 바꿉니다.</li>
</ul>

<h4>
  
  
  2. dfs 방법(첫 번째 DFS)
</h4>

<ul>
<li>
<p><strong>매개변수:</strong></p>

<ul>
<li>
$root: 현재 노드.</li>
<li>
$level: 트리의 현재 깊이 수준.</li>
<li>
&$levelSums: 합계가 저장될 배열에 대한 참조입니다.</li>
</ul>


</li>

<li><p><strong>기본 사례:</strong> 노드가 null인 경우 반환합니다.</p></li>

<li><p>현재 레벨의 합계가 초기화되지 않은 경우(즉, 해당 레벨이 배열에 존재하지 않는 경우) 0으로 초기화하세요.</p></li>

<li><p>현재 노드의 값을 해당 레벨의 합계에 더합니다.</p></li>

<li><p>왼쪽 및 오른쪽 하위 항목에 대해 반복적으로 dfs를 호출하여 레벨을 1씩 증가시킵니다.</p></li>

</ul>

<h4>
  
  
  3. 교체 방법(두 번째 DFS)
</h4>

<ul>
<li>
<p><strong>매개변수:</strong></p>

<ul>
<li>
$root: 현재 노드.</li>
<li>
$level: 현재 깊이 수준.</li>
<li>
$curr: 수정된 트리의 현재 노드.</li>
<li>
$levelSums: 각 레벨의 합계가 포함된 배열입니다.</li>
</ul>


</li>

<li>

<p>사촌의 가치 합계 계산:</p>

<ul>
<li>다음 레벨의 총합을 구하세요.</li>
<li>이 합계에서 현재 노드의 하위(형제) 값을 빼서 사촌의 합계를 구합니다.</li>
</ul>


</li>

<li><p>왼쪽 하위가 존재하는 경우 사촌의 합으로 새 TreeNode를 생성하고 이에 대해 재귀적으로 바꾸기를 호출합니다.</p></li>

<li><p>맞는 아이가 있다면, 맞는 아이에게도 똑같이 해주세요.</p></li>

</ul>

<h3>
  
  
  예제 연습
</h3>

<p>프롬프트의 첫 번째 예를 사용해 보겠습니다.</p>

<h4>
  
  
  입력
</h4>



<pre class="brush:php;toolbar:false">root = [5,4,9,1,10,null,7]

로그인 후 복사

첫 번째 DFS(레벨 합계 계산):
- 레벨 0: 5 → 합 = 5
- 레벨 1: 4 9 → 합 = 13
- 레벨 2: 1 10 7 → 합 = 18
- 최종 레벨합계: [5, 13, 18]
두 번째 DFS(값 바꾸기):
- 레벨 0: 5에는 사촌이 없습니다 → 0으로 바꿉니다.
- 레벨 1:
  - 4 → 사촌 = 9 → 9로 대체(전체 레벨 1에서 형제자매 없음).
  - 9 → 사촌 = 4 → 4로 대체.
- 레벨 2:
  - 1 → 사촌 = 10 7 = 17 → 17로 바꿉니다.
  - 10 → 사촌 = 1 7 = 8 → 8로 바꿉니다.
  - 7 → 사촌 = 1 10 = 11 → 11로 바꿉니다.

산출

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

class Solution {

    /**
     * @param TreeNode $root
     * @return TreeNode
     */
    public function replaceValueInTree($root) {
       ...
       ...
       ...
       /**
        * go to ./solution.php
        */
    }

    /**
     * DFS to calculate the sum of node values at each level.
     * @param $root - current node
     * @param $level - current depth level in the tree
     * @param $levelSums - array holding the sum of values at each level
     * @return void
     */
    private function dfs($root, $level, &$levelSums) {
       ...
       ...
       ...
       /**
        * go to ./solution.php
        */
    }

    /**
     * DFS to replace the node values with the sum of cousins' values.
     * @param $root - current node in the original tree
     * @param $level - current depth level in the tree
     * @param $curr - node being modified in the new tree
     * @param $levelSums - array holding the sum of values at each level
     * @return mixed
     */
    private function replace($root, $level, $curr, $levelSums) {
       ...
       ...
       ...
       /**
        * go to ./solution.php
        */
    }
}

// Helper function to print the tree (for testing purpose)
function printTree($root) {
    if ($root === null) return [];

    $result = [];
    $queue = [$root];

    while (!empty($queue)) {
        $node = array_shift($queue);
        if ($node !== null) {
            $result[] = $node->val;
            $queue[] = $node->left;
            $queue[] = $node->right;
        } else {
            $result[] = null;
        }
    }

    // Remove trailing null values for clean output
    while (end($result) === null) {
        array_pop($result);
    }

    return $result;
}

// Example usage:

// Tree: [5,4,9,1,10,null,7]
$root = new TreeNode(5);
$root->left = new TreeNode(4);
$root->right = new TreeNode(9);
$root->left->left = new TreeNode(1);
$root->left->right = new TreeNode(10);
$root->right->right = new TreeNode(7);

$solution = new Solution();
$modifiedTree = $solution->replaceValueInTree($root);

print_r(printTree($modifiedTree));  // Output: [0, 0, 0, 7, 7, null, 11]
?>

로그인 후 복사

사촌 값을 기반으로 한 이 단계별 교체로 인해 예와 같이 수정된 트리가 생성됩니다.