。等価な二分木を反転する

951。等価な二分木を反転

難易度: 中

トピック: ツリー、深さ優先検索、バイナリ ツリー

バイナリ ツリー T の場合、次のように 反転操作 を定義できます。任意のノードを選択し、左右の子サブツリーを交換します。

二分木 X は、X を Y と反転同等です。いくつかの反転操作の後、🎜>Y。

2 つのバイナリ ツリー root1 と root2 のルートを指定すると、2 つのツリーが反転等価であれば

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) を使用できます。考え方としては、2 つのツリーのルート値が同じで、サブツリーが (反転なしで) 同じであるか、いくつかのノードで左右の子を反転した後に同じになる場合、2 つのツリーは反転同等であるということです。

プラン：

1. 基本ケース:

   root1 と root2 の両方が null の場合、それらは自明に反転等価です。
   そのうちの 1 つだけが null の場合、それらは同等であることはできません。
   root1 と root2 のルート値が異なる場合、それらは等価であることはできません。

2. 再帰的なケース:

   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 の場合、または値が一致しない場合を処理します。
   • 再帰的なケースでは両方の可能性 (反転なしと反転) がチェックされ、どちらの条件下でもサブツリーが反転同等であることが保証されます。

時間計算量:

• この関数は両方のツリー内のすべてのノードをチェックし、各再帰呼び出しで 2 つのサブツリーを処理します。したがって、時間計算量は O(N) です。ここで、N はツリー内のノードの数です。

空間の複雑さ:

• 再帰的スタックのため、空間複雑度は O(H) です (H はツリーの高さです)。最悪の場合 (歪んだツリーの場合)、これは O(N) になる可能性があります。

連絡先リンク

このシリーズが役立つと思われた場合は、GitHub で リポジトリ にスターを付けるか、お気に入りのソーシャル ネットワークで投稿を共有することを検討してください。あなたのサポートは私にとって大きな意味を持ちます!

このような役立つコンテンツがさらに必要な場合は、お気軽にフォローしてください:

• LinkedIn
• GitHub

以上が。等価な二分木を反転するの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。