將所有節點放入堆棧中從根節點到目標節點的路徑

Question

如果需要將從目標節點到根節點的路徑中的所有節點都推送到目標節點，則需要將所有節點推入堆棧。 e.g我的樹是

  20 
     8  22 
    4  12 
2  1 

我的根節點是20，我的目標節點是4。因此，堆棧應該包含20,8和4。我試着拿出算法，但他們都失敗。任何建議？

Answer 1

我想出了以下解決方案。它將打印正確的解決方案，但唯一的問題是它會遍歷整個樹。

vector<int> store; 

void createStore(node* root,node* target){ if(root==NULL) 
        return; 
      else{ 
        store.push_back(root); 
        createStore(root->left,target); 
        createStore(root->right,target); 
      } 
      if(store[store.size()-1]==target) 
        return; 
      else{ 
        cout<<store[store.size()-1]->data<<endl; 
        store.pop_back(); 
      } 

Answer 2

首先找到目標節點。然後遍歷指向父節點的指針，直到到達根目錄。在遍歷每個鏈接時，將節點的值推入堆棧。

Answer 3

您可以在這裏使用遞歸。僞代碼如下：

bool found_target(node *root) 
{ 
    if (root->val == target || found_target(root->left) || found_target(root->left)) 
    { 
     push(root, stack); 
     return true; 
    } 
    return false; 
}