二分木の再帰的および非再帰的トラバーサルアルゴリズムテンプレート

[[423968]]

Leetcode を実践するには、いくつかのアルゴリズム テンプレートを知っておく必要があります。今回は、まず二分木の再帰的および非再帰的トラバーサル アルゴリズム テンプレートをまとめます。

バイナリ ツリーをトラバースする方法には、前方トラバース、中間トラバース、後方トラバース、レベル順トラバースの 4 つがあります。バイナリ ツリーのフロント、ミドル、バックの順序のトラバーサルでは、各トラバーサルを再帰的および循環的に実装することができ、各トラバーサルの再帰的実装は循環的実装よりも簡単です。以下に簡単にまとめておきます。私は「Code Thoughts」のハルビン工業大学の先輩の問題解決ガイドに深く感銘を受けました。そのため、以下のコードは「Code Thoughts」から一部引用したものです。

再帰

次の疑似コードは、二分木トラバーサルの再帰アルゴリズム テンプレートです。順序は中央、左、右で、前順序トラバーサルです。3 行のコード順序を変更することで、前順序、中央順序、後順序の 3 つの再帰トラバーサルを簡単に解決できます。

 def preorderTraversal(ルート: TreeNode) -> List[ int ]:
    解像度 = []
    defヘルプ(ルート):
        ルートでない場合は戻る 
        res.append(ルート.val) #
        help( root.left ) # 左
        ヘルプ( root.right ) # 右
    ヘルプ(ルート)
戻り値

これには C++ コードも用意されています。再帰アルゴリズム テンプレートには終了条件を追加する必要があります。そうしないと、再帰に入ると、深海に入るようなものになり、それ以降は、オファーは通行人になります。ソース コードのランダムな考え。

 void help(TreeNode * ルート、ベクトル< int > &res) {
    ルート == nullptr の場合 {
戻る;
    }
    res.push_back(root->val); // 中間
    help(root-> left ,res); // 左
    help(root-> right ,res); //右
} 
 
 
ベクトル< int > preorderTraversal(TreeNode* ルート) {
    ベクトル< int > res;
    ヘルプ(ルート、res);
 resを返します。
 }

反復

バイナリ ツリーの反復トラバーサルは、再帰トラバーサルよりも困難です。実際、スタック データ構造が使用されます。「Code Thoughts」では、マーキングにヌル ポインターを巧みに使用しています。原則として、処理されたノードをスタックに配置し、ヌル ポインターをマークとして配置します。

スタックは先入れ後出しの順序になっているため、事前順序トラバーサルの順序は左と右です。スタックに追加するときは、逆の順序で追加する必要があります。追加する各要素の後に null ポインターを追加します。Python では、代わりに None を使用することもできます。

以下は具体的な疑似コードです。インオーダートラバーサルとポストオーダートラバーサルについては、スタックにノードを追加する順序を変更するだけです。

 def preorderTraversal(ルート: TreeNode) -> List[ int ]:
      結果 = []
      st=[]
      # 1. ルートを決定する
      ルートの場合:
          st.append(ルート)
      一方、st:
          ノード = st.pop()
          ノードが None の場合:
              # 右、左、中央をスタックに追加し、中央、左、右を取り出します
              node.rightの場合: #right
                  st.append(ノード右)
              node.leftの場合: #left
                  st.append(ノード.left )
              st.append(ノード) #
              # ノードを記録するためにヌルポインタを追加します
              st.append(なし)
それ以外：
             # ノードはヌルポインタなので、次のノードが追加されます
              ノード = st.pop()
              結果を追加します(node.val)
結果を返す

以下は具体的な C++ コードです。C++ ではスタックにポップした後に戻り値がないので、特に注意が必要です。

ベクトル< int > preorderTraversal(TreeNode* ルート) {
        ベクトル< int >res;
        スタック<TreeNode*> st;
        ルートが nullptr ではない場合、st.push(root);
        while(!st.empty()){
            TreeNode* ノード = st.top ();
            if(ノード ​​!= nullptr){
                st.pop();
                if(node-> right ) st.push(node-> right );
                ノードが左にある場合、st.push(ノードが左にある)。
                st.push(ノード);
                st.push( NULL );
            }それ以外{
                // 特別な注意が必要
                st.pop();
                ノード = st.top ();
                st.pop();
                res.push_back(ノード->val);
            }
        }
 resを返します。 
     
    }

階層トラバーサル

実際、ツリー トラバーサルには、深さ優先トラバーサルと幅優先トラバーサルの 2 種類があります。ツリーのさまざまな深さ優先トラバーサル (前順序、内順序、後順序トラバーサル) は、再帰的および非再帰的な記述方法です。ツリー内の幅優先トラバーサルは、レベルごとのトラバーサルです。

バイナリ ツリーの階層的トラバーサルでは、トラバーサルを完了するためにキュー データ構造を使用する必要があります。

Pythonの擬似コードでは、

 def levelOrder(root: TreeNode) -> List[List[ int ]]:
 # 1. ルートを決定する
   ルートでない場合:
戻る[]
    # キューにルートを追加する
    quene = [ルート]
    出力リスト = []
    一方、クエン:
     # 最初のステップは長さを見つけることです
        長さ = len(キュー)
        in_list = []
 _が範囲内(長さ)の場合:
         # C++では2行必要
            curnode = queue.pop(0) # (デフォルトではリストの最後の要素を削除します) ここではキューの先頭にある要素を削除する必要があります
            in_list.append(curnode.val)
            curnode.leftの場合: queue.append( curnode.left )
            curnode.rightの場合: queue.append( curnode.right )
        out_list.append(in_list)
 out_listを返す

上記の Python 疑似コードを使用して、より効率的な C++ コードを記述します。

クラスソリューション{
公共：
    ベクトル<ベクトル< int >> レベルオーダー(TreeNode* ルート) {
        ベクトル<ベクトル< int >> res;
        キュー<TreeNode*> que;
        // ルートを決定する
        root != nullptr の場合、que.push(root);
        while(!que.empty()) {
             // まずキューの長さを調べます
整数 サイズ= que.size ( );
            ベクトル< int > vec;
            // 反復してノード要素を追加する
( int i = 0 ; i<サイズ; i++) {
                TreeNode* ノード = que.front();
                que.pop();
                vec.push_back(ノード->val);
                if (node-> left ) que.push(node-> left );
                node-> rightの場合、que.push(node-> right ) を実行します。
            }
            res.push_back(vec);
        }
 resを返します。
    }
 };

上記はツリートラバーサルテンプレートです。実際、これは本質的には深さ優先探索と幅優先探索のアルゴリズム テンプレートです。他の多くの操作はツリー探索操作に基づいています。したがって、すべてのツリー探索方法を習得することは、ツリー問題の半分を解決することと同じです。