1

これは在宅ワークではありません。ツリートラバーサルでいくつかの新しい質問を考えていましたが、これは非常に明白であるように思われるので、解決することを考えました。

質問は、BFS のようなレベル オーダー トラバーサルに非常に似ています。BFS では通常、ツリーの各レベルで左から右に移動しますが、ここでレベル i で左から右に移動する場合、レベル (i-1) と (i+1) は右から左に移動する必要があります。

例えば：

           2
          / \
         7   5
        / \   \
       2   6   9
          / \   \
         5  11   4

通常の BFS では、2、7、5、2、6、9、5、11、4 を出力します。

しかし、私は出力するソリューションを探しています: 2, 5, 7, 2, 6, 9, 4, 11, 5

私は解決策を思いつくことができます。しかし、私は誰かが私のものよりも良い解決策を思いつくかどうかを見たい. 特に、スペースの複雑さ (スタック サイズ) の最適化も検討しています。

C++言語に合わせてロジックを入力してください。ソリューションでコンテナーや STL を使用していない場合は、非常にありがたいです。

ここのコメントに基づいて、2 つのスタックを使用したソリューションを考え出しました。私の解決策は以下の通りです。

  • スタック S1 と S2 を作成し、キュー Q を作成します。キュー Q は最終的な ans を保持します。
  • スタック (S1 または S2) をプッシュする前に、まずそれをキュー Q に入れることに注意してください。
  • スタック s1 から何をポップしても、その (最初の) 右の子と (次に) 左の子を (この順序で) スタック s2 にプッシュします。（ポイント2を覚えておいてください）
  • スタック s2 からポップするものは何でも、その (最初の) 左の子と (次に) 右の子を (この順序で) スタック s1 にプッシュします。（ポイント2を覚えておいてください）
  • 1 つのスタックからポップし、両方のスタックが空になるまで別のスタックにプッシュします。Queue の最終エントリは ans になります。
/*
Create Stack S1, S2; // for tmp itr. Both of size log<n>
Create Queue Q; // It will hold ans
*/ 


Q.enqueue(root); //Enqueue the root nood;
S1.enqueue(root); //Fill the stack with somthing to start.



  while(S1||S2){                        // keep spinning untill both stack are empty.
        while(s1){                      //take care of stack S1.
            Node* tmp = S1.pop();       //take top elem;

        if(tmp->right){
            Q.enqueue(tmp->right);
            S2.push(tmp->right);
        }

        if(tmp->left){
            Q.enqueue(tmp->left);
            S2.push(tmp->left);
        }
    }

    while(S2){ //while S2 is not empty
        Node* tmp = S2.pop();

        if(tmp->left){
            Q.enqueue(tmp->left);
            S1.push(tmp->left);
        }

        if(tmp->right){
            Q.enqueue(tmp->right);
            S1.push(tmp->right);
        }

    }
} //End of outher while

while(Q){
    cout<< Q.pop()->data;   //output the entries in desired format.
}

私には問題ないようです（そうでない場合はお知らせください）。しかし、他に可能な解決策があるかどうかはまだ疑問です（これよりも優れています）。

4

3 に答える 3

2

単一のキューを使用するのではなく、スタックのペアを使用します。現在のスタックが空になったら、他のスタックからノードをポップし始め、子を空になったスタックにプッシュします。

だからあなたは

  • 2をスタックの1つにプッシュします。
  • それから2をポップし、75を他の1つに押します。スタックを交換します。
  • ポップ5、プッシュ9。
  • ポップ7、プッシュ62.スタックを交換します。

等。

最初に左または右のどちらを押すかを決定するには、状態変数も必要です。

于 2010-10-05T20:19:40.363 に答える
1

上記の Potatoswatter の提案を C# で試してみましたが、まだ実行していません。何かを変更する必要がある場合は、修正してください。

void BFSTraversePrintzigzag(Node root)  

{  
    bool bLeftToRight = true;  
    Stack<Node> stack1=new Stack<Node>();  
    Stack<Node> stack2=new Stack<Node>();  
    stack1.Push(root);  
    //loop until both the stacks are empty  
    while(stack1.Count>0 ||stack2.Count>0)  
    {  
        //Stack1 will be empty when all the nodes on a level are traversed.   
        if (stack1.Count==0 && stack2.Count>0)  
        {  
            //Swap stack1 and stack2, if stack1 is empty  
            stack1= stack2;  
            while(stack2.Count>0)  
                stack2.Pop();  
            bLeftToRight=!bLeftToRight;  
            //This is the state variable to switch the order from left to right and from Right to left  
        }  
        root=stack1.Pop();  
        Console.WriteLine(root.data) ;  
        if(bLeftToRight)      
        {        
            if(root.left!=null)  
                stack2.Push(root.left);  
            if(root.right!=null)  
                stack2.Push(root.right);  
        }  
        else  
        {  
            if(root.right!=null)  
                stack2.Push(root.right);  
            if(root.left!=null)  
                stack2.Push(root.left);  
        }  
    }  
}
于 2012-09-09T12:20:52.203 に答える
0

あなたが何を望んでいるのか理解できれば、スタックの代わりに優先キューを使用します。優先キューのキーとして、ノードのツリーにレベルを保存し、そのレベル内の順序を保存する必要があります。比較機能は、レベルを主キーとして使用します。偶数レベルの場合は、順序を直接2次キーとして使用しますが、奇数レベルの場合は、順序を無効にします。ツリーのルートをレベル0とレベル1のどちらと見なすかによって、直接使用されるレベルと否定されるレベルを逆にする必要がある場合があります。

于 2010-10-05T20:36:54.680 に答える