技術共有

このアルゴリズムは、質問の 42 レコードを推定しようとします [101. 対称二分木、100. 同一の木、572. 別の木のサブツリー]

2024-07-12

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

序文

バイナリ ツリーの章では、バイナリ ツリーの操作の練習を開始します。
レコード 42 [101. 対称二分木]。
続く。

1. トピックの読み方

バイナリ ツリーのルート ノードのルートを指定します。 軸対称かどうかを確認する。

例 1:
ここに画像の説明を挿入します

输入：root = [1,2,2,3,4,4,3]
输出：true

  • 1
  • 2

例 2:
ここに画像の説明を挿入します

输入：root = [1,2,2,null,3,null,3]
输出：false

  • 1
  • 2

ヒント：

树中节点数目在范围 [1, 1000] 内
-100 <= Node.val <= 100

  • 1
  • 2

上級: 使用できます再帰と反復この問題を解決するには 2 つの方法がありますか?

2. 実現しようとする

アイデア 1

まずは再帰を使ってみてください。 Core: 軸対称性を判断する基準は何ですか?

再帰: 自分自身に電話をかけます。重複するロジックはまだ見つかりません：

  • 左==右を決定しますか?サブツリーの入力が間違っています。
  • 左側のサブツリーは左、中央に移動し、右側のサブツリーは右、左、中央に移動します。シーケンスは等しいですか?しかし、それは木全体に対するものです。サブツリーに入るのも間違っています。

アイデア 2

変更するには反復的なアプローチを使用します。レベル順のトラバーサルを使用します。
層順序の結果が得られた後、各層は偶数であり、反転後に等しいと判断されます。ただし、たとえば 2 つ目は、null ポインターが除外されるため、これは当てはまりません。
その考えは機能しません。

要約:対称性を探す必要があることはわかっていますが、対称性を判断するための統一された基準はありません。。

3.参考アイデア

参考リンク

学習内容

  • 軸対称: ルート ノードの左右のサブツリーを反転して等しくすることはできますか? 、どうやって比較するのですか？
  • 説明から得たもの正しい考え: この走査には、ルート ノードの左側のサブツリーとルート ノードの右側のサブツリーが必要です。同時に横断する 。 2 つのサブツリーを一度に走査することによってのみ、両側のノードが等しいかどうかを判断できます。
    • まず、左側のサブツリーの左側と右側のサブツリーの右側を通過します。このとき、外側のノードは等しいと判断されます。
    • 次に、左側のサブツリーの右側と右側のサブツリーの左側を通過します。この時点で、内部ノードは等しいと判断されます。
    • 両方が返された後は、両方とも同時に true となり、対称性を示します。
  • 走査順序を決定します: 左、右、中央。左側の子を処理した後、再度右側の子を処理し、結果を中央のノードに返します。
  • 実装しようとしていますアイデアの不十分さ : ルート ノードの左側のサブツリーのみを処理し、ルート ノードの右側のサブツリーの順序が左側のサブツリーと異なることを確認します。走査順序を反転したり、その他のことを行っても、統一されたロジックを取得することはできません。

再帰的な実装

すべてのコメントはアイデアです。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool iscompare(TreeNode* left,TreeNode* right){ //两边同时遍历，所以两个参数。返回是否相等，用bool类型。
        //确定终止条件
        if(!left && !right) return true;    //同时为空，可以翻转
        else if(!left && right) return false; //一个空，一个不为空。肯定不等
        else if (!right && left) return false;//一个空，一个不为空。肯定不等
        else if(left->val != right->val) return false;//都不为空，但是值不等

        //都不为空，值相等。说明可以继续进行外侧比较、内侧比较，不用return。
        bool outside = iscompare(left->left,right->right);  //同时比较，解决了左右遍历顺序不一样
        bool inside = iscompare(left->right,right->left);
        return outside && inside;   //同时返回true。才能返回true
    }
    bool isSymmetric(TreeNode* root) {
        return iscompare(root->left,root->right);
    }
};

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29

ツリー (左のサブツリー) の走査順序は左-中央であり、ツリー (右のサブツリー) の走査順序は右-左-中央です。

反復的なアイデア 1

  • ルート ノードの左側のサブツリーとルート ノードの右側のサブツリーを同時に処理します。前回の縦走とは違います。
  • キュー構造を使用: put比較される 2 つのノードが同時にキューに入れられます、また同時に取り出します 。抽出された 2 つのノードを反転できるかどうかを判断します。したがって、左右の子が空いている場合は、それらもキューに入れる必要があります。
  • スタック構造を使用します。それでも 2 つのノードを同時に処理する必要があります。比較するオブジェクトが 2 つあります。 同時に入れる、同時に取り出す。

反復実装 [キュー構造]

スタック構造も同じです。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if(!root) return false;
        queue<TreeNode*> que;
        que.push(root->left);//放入左子树
        que.push(root->right);//放入右子树
        while(!que.empty()){
            TreeNode* left = que.front(); que.pop();//取出比较对象中的左节点
            TreeNode* right = que.front();que.pop();//取出比较对象中的右节点

            if(!left && !right){    //都是空节点
                continue;
            }else if(!left || !right || left->val != right->val){
                return false;
            }

            que.push(left->left);
            que.push(right->right);
            que.push(left->right);
            que.push(right->left);
        }
        return true;
    }
};

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36

概要 [軸対称二分木]:

  • まだ横断的ですが、違いは次のとおりです。両方のサブツリーを同時に走査する必要がある 。サブツリーを深く再帰することは正しくありません。
  • オブジェクトを比較して true を判定する条件: 両方が空であるか、値が等しい。残りは偽です。
  • また、左側と右側の順序が異なるため、サブツリーを再帰的に走査することもできません。
  • これはレベル順のトラバースではありません。レイヤーを順番に走査する必要がある場合: 各レイヤーの結果を取得し、逆にそれらが等しいかどうかを確認します。以下のように (推奨されません)、上記の答えはすべて非常に優れています。
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        vector<vector<int>> level;
        queue<TreeNode*> que;
        if(!root) return false;
        que.push(root);
        while(!que.empty()){
            int size = que.size();
            vector<int> vec;
            while(size--){
                TreeNode* cur = que.front();que.pop();
                if(cur){ //不是空节点
                    que.push(cur->left);
                    que.push(cur->right);
                    vec.push_back(cur->val);
                }else{
                    vec.push_back(INT_MIN);//因为节点的值【-100,100】。用一个最小值代表空。
                }
            }
            level.push_back(vec);
        }
        //获得层序遍历。包含空。空的数值借助INT_MIN代替。
        for(int i = 1;i < level.size();i++){
            vector<int> temp = level[i];
            reverse(temp.begin(),temp.end());
            if(temp != level[i]){
                return false;
            }
        }
        return true;

    }
};

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45

質問練習

【100.同じ木】

1. タイトル

2 つのバイナリ ツリーのルート ノード p と q を指定して、2 つのツリーが同じかどうかをテストする関数を作成します。

木が2本なら構造的に同じであり、ノードの値も同じです、それらは同じであるとみなされます。

例 1:

输入：p = [1,2,3], q = [1,2,3]
输出：true

  • 1
  • 2

例 2:

输入：p = [1,2], q = [1,null,2]
输出：false

  • 1
  • 2

例 3:

输入：p = [1,2,1], q = [1,1,2]
输出：false

  • 1
  • 2

ヒント：

两棵树上的节点数目都在范围 [0, 100] 内
-10^4 <= Node.val <= 10^4

  • 1
  • 2

アイデア

2 つのツリーが同じかどうかを判断します。構造は同じで、値も同じです。

  • それなら、そうする必要があります2 つのツリーが同時に処理される場合にのみ、比較オブジェクトが存在します。 。ツリーを深くトラバースしたり、ツリー上で何らかの操作を実行したりするだけでは役に立ちません。
  • 「101.対称二分木」との違い、比較対象。ここ比較オブジェクトの左の子は左の子と比較され、右の子は右の子と比較されます。 。再帰呼び出しのパラメータが指定されます。

コード

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if(!p && !q) return true;  //传入节点同时为空，可以对应
        else if(!p && q) return false;//一个空，另一个不是空。不可能对应。
        else if(p && !q) return false;//一个空，另一个不是空。不可能对应。
        else if(p->val != q->val) return false;//值不等，不可能对应。

        bool leftchild = isSameTree(p->left,q->left); 
        bool rightchild = isSameTree(p->right,q->right);
        return leftchild && rightchild;
    }
};

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24

【572.別の木の部分木】

トピック

2 つのバイナリ ツリーのルートとサブルートが与えられます。ルートに次のものが含まれ、サブルートに次のものが含まれているかどうかを確認します。同じ構造とノード値サブツリー。存在する場合は true を返し、存在しない場合は false を返します。

二分木のサブツリーには、ツリーのノードとこのノードのすべての子孫ノードが含まれます。 ツリーはそれ自体のサブツリーとして表示することもできます。

例 1:

输入：root = [3,4,5,1,2], subRoot = [4,1,2]
输出：true

  • 1
  • 2

例 2:

输入：root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]
输出：false

  • 1
  • 2

ヒント：

root 树上的节点数量范围是 [1, 2000]
subRoot 树上的节点数量范围是 [1, 1000]
-10^4 <= root.val <= 10^4
-10^4 <= subRoot.val <= 10^4

  • 1
  • 2
  • 3
  • 4

アイデア

(1) サブツリーも 2 つのツリーが等しいと判断します。同等判定は「100.質問コード実装」を利用して解くことができます。
(2) ただし、ルート内に存在する必要がありますsubRoot ルート ノードの値と等しいノードをサブツリーのルート ノードとして使用します。レベル順序を使用してルートをたどります。

コード

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isSame(TreeNode* rootnode,TreeNode* subRootnode){
        if(!rootnode && !subRootnode) return true;
        else if(!rootnode && subRootnode) return false;
        else if(rootnode && !subRootnode) return false;
        else if(rootnode->val != subRootnode->val) return false;

        bool leftchild = isSame(rootnode->left,subRootnode->left);
        bool rightchild = isSame(rootnode->right,subRootnode->right);
        return leftchild && rightchild;
    }
    bool isSubtree(TreeNode* root, TreeNode* subRoot) {
        //先找到和subRoot值相等的节点，才有可能相等。得遍历root找到和subRoot值相等的节点，可能作为子树的根节点

        //用层序遍历
        queue<TreeNode*> que;
        que.push(root);
        while(!que.empty()){
            int size = que.size();
            while(size--){
                TreeNode* cur = que.front();que.pop();
                if(cur->val == subRoot->val){
                    bool subtree = isSame(cur,subRoot);
                    if(subtree) return true;
                }
                if(cur->left) que.push(cur->left);
                if(cur->right) que.push(cur->right);
            }
        }
        return false;
    }
};

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44

全文要約

コア: 2 つのツリーを同時に走査して、比較オブジェクトを決定します。再帰的な実装を実行します。

深いツリーのトラバースでは、オブジェクトの両側の比較は行われません。

（訂正は歓迎しますが、転載の際は出典を明記してください）

個人プロフィール

彼は 30 年以上テクノロジーの研究に専念しており、java、linux、javascript、php、css などのさまざまな言語に堪能であり、オープンソース分野で多くの貢献を行っています。将来の参考のために技術開発におけるいくつかの問題を共有する開発者ドキュメント ステーション。

プライベートな連絡先の最初の情報

送料