スタック内のリーフ値を持つバイナリツリーパスを出力します。

Question

リーフノード値を使用してバイナリツリーパスを出力するには、次のように入力します。バックトラックするとスタックから '3'が削除されます。どのように達成するためにコードを変更するには？私はスタックから値をポップする場所を見つけることができません。

// should print out "5 8 10", but it prints "5 3 8 10" 
printPathWithStack(root, 5); 

     10 
    / \ 
    8  2 
/\ /
3 5 4 

void printPathWithStack(Node root, int key) 
{ 
    Stack<Node> path = new Stack<Node>(); 
    printPathWithStackHelper(root, key, path); 
} 

void printPathWithStackHelper(Node root, int key, Stack<Node> path) 
{ 
    if (root == null) { 
     return; 
    } 

    path.push(root); 

    if (root.data == key && root.left == null && root.right == null) { 
     while (!path.isEmpty()) { 
      System.out.print(path.pop().data + " "); 
     } 
    } else if (root.left == null && root.right == null){ 
      path.pop(); 
    } 

    printPathWithStackHelper(root.left, key, path); 
    printPathWithStackHelper(root.right, key, path); 
} 

Answer 1

このようにスタックを使用するのは少し奇妙です。

しかし、バックトラックするときは、item.leftまたはitem.rightが最後に取得したアイテムと等しくないすべてのアイテムを単に破棄する必要があります。これはあなたにルートへのパスを与えます。

Answer 2

左と右の子への再帰呼び出しを行うまで、スタックへのプッシュを延期することができます。

if (root.data == key && root.left == null && root.right == null) 
{ 
    path.push(root); 
    while (!path.isEmpty()) 
    { 
     System.out.print(path.pop().data + " "); 
    } 
    return; 
} 
else if (root.left == null && root.right == null) 
{ 
     return; 
} 
path.push(root); 
printPathWithStackHelper(root.left, key, path); 
printPathWithStackHelper(root.right, key, path); 

あなたの問題に対処してください。

P.S.一般的なケースのコードフラグメントはテストされていませんが、あなたが必要とすることを願っています:)