c++ - 打印给定总和的所有路径的函数(二叉树 C++)

Question

"给定一个二叉树和一个整数k。编写一个函数来打印 树中的每条路径，路径中的节点之和为 k。假设一条路径可以从任意节点开始，到任意节点结束，即它们不必是根节点和叶节点；树中也可以有负数。”

我仍然坚持遍历树以实现此目标背后的逻辑。任何帮助/提示将不胜感激!

Answer 1

logic behind traversing a tree to achieve this goal

使用深度优先或广度优先搜索来访问树中的每个节点。

在每个节点开始新的搜索。

因为这棵树是一个递归的数据结构，所以我会用递归来进行查找。

并结束递归:- 更新 03/14

1) 在叶节点。

当找到目标总和时不是，因为存在负值

不是当总和超过目标总和时，因为存在负值

注意:我认为这大大简化了“求和”操作。它现在是一个 DF 搜索，在叶子上终止，在特定节点上有简单的输出。

不需要“decurse”操作，因为所有分支都将通过 DF/BF 访问进行探索。

---

更新 3/18

我的代码的一些示例输出。

'on-its-side' 树显示(从上到左)

               '-3' 
          '-2' 
               '-1' 
     '0' 
               '1' 
          '2' 
                    '3' 
               '4' 
'5' 
               '6' 
          '7' 
                    '8' 
               '9' 
     '10' 
               '11' 
          '12' 
                    '13' 
               '14' 
                    '42' 

示例“targetSum”结果:(41 个中的 5 个)

BTree_t::dfVisit(-2)  
  start level 3:    -2 
  start level 2:     0   -2 

BTree_t::dfVisit(-1)  
  start level 4:    -1 

BTree_t::dfVisit(0)  
  start level 2:     0 
  start level 1:     5    0   -2   -3 

BTree_t::dfVisit(1)  
  start level 4:     1

---

2017/03/22 更新

网络上有大量深度优先搜索代码示例。在我的方法中，树贡献只是从根开始搜索(或解释为什么不能)。

// depth-first-visit of all nodes in tree
void BTree_t::dfVisitSum(const int targetSum)
{
   std::cout << "\n\n  BTree_t::dfVisitSum(" << targetSum << ") ";

   if(m_root)
   {
      int reportCount = m_root->dfVisitSum(targetSum);
      if(0 == reportCount)
         std::cout << "none";
    }
    else
    {
      std::cerr << "\n  dfVisitSum() Note: tree has no elements.."
                << std::endl;
   }
}

如果我们现在查看节点 dfVisitSum()，我们注意到它有一个有限的持续时间“nodeLog”传递到 sumSearch():

// depth-first-visit of all nodes below the current node
int Node_t::dfVisitSum(const int targetSum)
{
   int reportCount = 0;

   // dfs search left, then do something, then search right
   if(m_left)  {  reportCount += m_left->dfVisitSum(targetSum); }

   {
      // while visiting this node, create a vector for logging 
      NVec_t  nodeLog;   
      nodeLog.reserve(nodeDepthMax()); 

      // start a new depth-first-search called "sumSearch()
      reportCount += sumSearch(targetSum, nodeLog);  

   }  // nodeLog terminates here

   if(m_right) { reportCount += m_right->dfVisitSum(targetSum); }

   return (reportCount);
}

最后，

// target-sum-search
int Node_t::sumSearch(const int targetSum, NVec_t& nodeLog)
{
   int reportCount = 0;

   // capture visit of this node to log
   nodeLog.push_back(this); 

   // in dfs style, first search down the left 
   if(m_left)  {  reportCount += m_left->sumSearch(targetSum, nodeLog); }

   { // now do something in this node
      size_t   startLvl = nodeLog[0]->m_lvl; // for report

      int accumulateSum = 0;
      for (size_t i = 0; i < nodeLog.size(); ++i)
         accumulateSum += nodeLog[i]->m_payLoad;
      // sure, sure, use std::accumulate with a lambda, if you wish

      if (targetSum == accumulateSum)
      {
         std::stringstream reportLabelSS; // convenience
         reportLabelSS << "\n     @ level " << startLvl << ":";
         std::cout << showNVec(nodeLog, reportLabelSS.str());
         // this output displays start level and nodes-visited payloads
         reportCount += 1;  // report occurrence north bound to caller
      }
   }
   // in dfs style, search down the right
   if(m_right) { reportCount += m_right->sumSearch(targetSum, nodeLog); }

   // discard / clear  this node visit from log, we are out-a-here
   nodeLog.pop_back(); // removes last nodeLog element
   return(reportCount); // report count
}