Sepupu dalam Pokok Binari II-tutorial php-php.cn

2641. Sepupu dalam Pokok Binari II

Kesukaran: Sederhana

Topik: Jadual Hash, Pokok, Carian Pertama Kedalaman, Carian Luas-Pertama, Pokok Binari

Memandangkan akar pokok binari, gantikan nilai setiap nod dalam pokok itu dengan jumlah semua nilai sepupunya.

Dua nod pokok binari ialah sepupu jika mereka mempunyai kedalaman yang sama dengan ibu bapa yang berbeza.

Kembalikan akar pokok yang diubah suai.

Perhatikan bahawa kedalaman nod ialah bilangan tepi dalam laluan dari nod akar kepadanya.

Contoh 1:

Cousins in Binary Tree II

Input: punca = [5,4,9,1,10,null,7]
Output: [0,0,0,7,7,null,11]
Penjelasan: Rajah di atas menunjukkan pokok binari awal dan pokok binari selepas menukar nilai setiap nod.
- Nod dengan nilai 5 tidak mempunyai sepupu jadi jumlahnya ialah 0.
- Nod dengan nilai 4 tidak mempunyai sepupu jadi jumlahnya ialah 0.
- Nod dengan nilai 9 tidak mempunyai sepupu jadi jumlahnya ialah 0.
- Nod dengan nilai 1 mempunyai sepupu dengan nilai 7 jadi jumlahnya ialah 7.
- Nod dengan nilai 10 mempunyai sepupu dengan nilai 7 jadi jumlahnya ialah 7.
- Nod dengan nilai 7 mempunyai sepupu dengan nilai 1 dan 10 jadi jumlahnya ialah 11.

Contoh 2:

Cousins in Binary Tree II

Input: akar = [3,1,2]
Output: [0,0,0]
Penjelasan: Rajah di atas menunjukkan pokok binari awal dan pokok binari selepas menukar nilai setiap nod.
- Nod dengan nilai 3 tidak mempunyai sepupu jadi jumlahnya ialah 0.
- Nod dengan nilai 1 tidak mempunyai sepupu jadi jumlahnya ialah 0.
- Nod dengan nilai 2 tidak mempunyai sepupu jadi jumlahnya ialah 0.

Kekangan:

Bilangan nod dalam pokok adalah dalam julat [1, 10⁵].
1 <= Node.val <= 10⁴

Petunjuk:

Gunakan DFS dua kali.
Buat pertama kali, cari jumlah nilai semua peringkat pokok binari.
Untuk kali kedua, kemas kini nilai nod dengan jumlah nilai tahap semasa - nilai nod adik beradik.

Penyelesaian:

Penyelesaian menggunakan pendekatan Depth-First Search (DFS) dua kali:

DFS Pertama: Kira jumlah semua nilai nod pada setiap peringkat pepohon.
DFS Kedua: Kemas kini nilai setiap nod dengan jumlah nilai sepupunya dengan menolak nilai adik-beradiknya daripada jumlah untuk tahap itu.

Mari laksanakan penyelesaian ini dalam PHP: 2641. Sepupu dalam Pokok Binari 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>
  
  
  Pecahan Kod
</h3>

<h4>
  
  
  1. replaceValueInTree Kaedah
</h4>

<ul>
<li>Ini ialah kaedah utama yang memulakan proses.</li>
<li>Ia mencipta tatasusunan kosong, $levelSums, untuk menyimpan jumlah nilai pada setiap peringkat.</li>
<li>Ia memanggil DFS pertama untuk mengisi $levelSums dan kemudian memanggil DFS kedua untuk menggantikan nilai dalam pepohon.</li>
</ul>

<h4>
  
  
  2. Kaedah dfs (DFS Pertama)
</h4>

<ul>
<li>
<p><strong>Parameter:</strong></p>

<ul>
<li>
$root: Nod semasa.</li>
<li>
$level: Paras kedalaman semasa pokok.</li>
<li>
&$levelSums: Rujukan kepada tatasusunan tempat jumlah akan disimpan.</li>
</ul>


</li>

<li><p><strong>Kes Asas:</strong> Jika nod adalah batal, kembalikan.</p></li>

<li><p>Jika jumlah tahap semasa tidak dimulakan (iaitu, tahap tidak wujud dalam tatasusunan), mulakan ia kepada 0.</p></li>

<li><p>Tambahkan nilai nod semasa pada jumlah untuk tahapnya.</p></li>

<li><p>Panggil dfs secara rekursif untuk anak kiri dan kanan, menambah tahap sebanyak 1.</p></li>

</ul>

<h4>
  
  
  3. gantikan Kaedah (DFS Kedua)
</h4>

<ul>
<li>
<p><strong>Parameter:</strong></p>

<ul>
<li>
$root: Nod semasa.</li>
<li>
$level: Tahap kedalaman semasa.</li>
<li>
$curr: Nod semasa dalam pokok yang diubah suai.</li>
<li>
$levelSums: Tatasusunan dengan jumlah untuk setiap tahap.</li>
</ul>


</li>

<li>

<p>Kira jumlah nilai sepupu:</p>

<ul>
<li>Dapatkan jumlah keseluruhan untuk peringkat seterusnya.</li>
<li>Tolak nilai anak nod semasa (adik beradik) daripada jumlah ini untuk mendapatkan jumlah sepupu.</li>
</ul>


</li>

<li><p>Jika anak kiri wujud, buat TreeNode baharu dengan jumlah sepupu dan panggil ganti secara rekursif.</p></li>

<li><p>Jika anak yang betul wujud, lakukan perkara yang sama untuk anak yang betul.</p></li>

</ul>

<h3>
  
  
  Contoh Panduan
</h3>

<p>Mari kita gunakan contoh pertama daripada gesaan:</p>

<h4>
  
  
  Input
</h4>



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

Salin selepas log masuk

DFS Pertama (Kira Jumlah Tahap):
- Tahap 0: 5 → Jumlah = 5
- Tahap 1: 4 9 → Jumlah = 13
- Tahap 2: 1 10 7 → Jumlah = 18
- Jumlah peringkat akhir: [5, 13, 18]
DFS Kedua (Nilai Ganti):
- Pada Tahap 0: 5 tidak mempunyai sepupu → Gantikan dengan 0.
- Pada Tahap 1:
  - 4 → Sepupu = 9 → Gantikan dengan 9 (daripada Tahap 1 jumlah, tiada adik beradik).
  - 9 → Cousins = 4 → Gantikan dengan 4.
- Pada Tahap 2:
  - 1 → Sepupu = 10 7 = 17 → Gantikan dengan 17.
  - 10 → Sepupu = 1 7 = 8 → Gantikan dengan 8.
  - 7 → Sepupu = 1 10 = 11 → Gantikan dengan 11.

Output

<?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]
?>

Salin selepas log masuk

Penggantian langkah demi langkah berdasarkan nilai sepupu ini menghasilkan pokok yang diubah suai seperti yang ditunjukkan dalam contoh.

Ringkasan

Penyelesaian menggunakan dua traversal DFS: satu untuk mengira jumlah dan satu lagi untuk menggantikan nilai nod.
Logik memastikan setiap nod dikemas kini berdasarkan nilai nod sepupunya sambil mengekalkan struktur pokok binari.

Pautan Kenalan

Jika anda mendapati siri ini membantu, sila pertimbangkan untuk memberi repositori bintang di GitHub atau berkongsi siaran pada rangkaian sosial kegemaran anda ?. Sokongan anda amat bermakna bagi saya!

Jika anda mahukan kandungan yang lebih berguna seperti ini, sila ikuti saya: