ベクトル要素のポップについて

Question

次のコードは、特定のsumに等しいすべてのルートからリーフパスを検索するために使用され、バイナリツリーとsumが与えられています。

class Solution { 
public: 
    void buildResult(std::vector< std::vector<int> >& result, std::vector<int>& ans, TreeNode* root, int sum) { 
     if(!root) 
      return; 

     ans.push_back(root->val); 
     if(root->val==sum && !root->left && !root->right) 
      result.push_back(ans); 
     buildResult(result, ans, root->left, sum-(root->val)); 
     buildResult(result, ans, root->right, sum-(root->val)); 
     ans.pop_back(); 
    } 

    vector<vector<int>> pathSum(TreeNode* root, int sum) { 
     std::vector< vector<int> > result; 
     std::vector<int> ans; 

     if(!root) 
      return result; 

     buildResult(result, ans, root, sum); 
     return result; 
    } 
}; 

上記のコードは動作し、期待される出力を生成します。しかし、私は文の使用を理解していませんans.pop_back(); - 私はそれがバックトラックのためだと理解していますが、正確にこのバックトラックが行われたのですか？これらの値は、有効なパス上にあるかどうかを確認する前に、ベクトルansに挿入されています。さらに、pop_back()の数は、間違った合計につながる数字がいくつ挿入されたかによって多くなるはずです。誰かが私にこのことを説明してくれますか？

ありがとうございます！

Answer 1

バックトラックは、再帰関数が返すことによって実行されます。

再帰関数は、現在のノードをansにプッシュすることによって、そのパスをツリーを横切って記録しています。それが葉に到達すると、リーフの値をチェックし、一致する場合は、ansをresultにプッシュすることによって、それが作成したばかりのパスを記録します。

ansは、現在のノードのパンクランプトレールと考えることができます。再帰関数がツリー内のノードに入るたびに、現在のノードの値をansにプッシュし、右側のリーフに達すると、ブレッドクラムの末尾がリーフノードへのパスになります。

したがって、再帰関数は、現在のノードを返します。再帰呼び出しから戻ることによって、再帰関数はその親に戻ります。しかし、ブレッドクラムの現在の尾から最後のブレッドクラムを削除する前に、ブレッドクラムの軌跡を元に戻ってきた親のパスだけに戻すことはできません。