在二元树中找出和为某一值的所有路径（树）

迈不过友情╰ 2022-03-21 11:20 109阅读 0赞

**问题：**输入一个整数和一棵二元树。从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径。打印出和与输入整数相等的所有路径。  
        例如输入整数 22 ，如下图二元树：  
                                            10  
                                           /     \\  
                                          5     12  
                                        /    \\     
                                       4     7

则打印出两条路径：10, 12和10, 5, 7。

二元树节点的数据结构定义为：

struct BinaryTreeNode // a node in the binary tree
    {
    int m_nValue; // value of node
    BinaryTreeNode *m_pLeft; // left child of node
    BinaryTreeNode *m_pRight; // right child of node
    };

**   
分析：**

**思路一**

1、当访问到某一节点时，把该结点的值添加到当前和变量，且把该结点压入栈中。

2、若结点为叶子结点，且当前和变量等于期望的和，则打印栈中的结点值，即为所需的路径。

3、若结点不是叶子结点，继续访问它的左孩子结点，访问它的右孩子结点。

4、删除该结点。包括从当前和变量中减去结点值，从栈中弹出结点值。此时，已回到父结点。

void findPath(BinaryTreeNode *pTreeNode,
             int expectedSum,
             vector<int>& path,
             int & currentSum)
     {
         if( !pTreeNode )
             return;//结点值添加至当前和变量中//结点压入栈中
         currentSum += pTreeNode->m_nValue;
         path.push_back(pTreeNode->m_nValue);
         bool isLeaf = !(pTreeNode->m_pLeft) && !(pTreeNode->m_pRight);//当前结点为叶子结点，且和为期望值，打印路径
         if(currentSum == expectedSum && isLeaf)
         {
             vector<int>::iterator iter;
             for(iter = path.begin(); iter != path.end(); iter++)
             {
                 cout << *iter << "\t";
             }
             cout << endl;
         }//当前结点不为叶子结点，查找它的左右孩子结点
         if(pTreeNode->m_pLeft)
             findPath(pTreeNode->m_pLeft, expectedSum, path, currentSum);
         if(pTreeNode->m_pRight)
             findPath(pTreeNode->m_pRight, expectedSum, path, currentSum);
     //当前结点删除，退至其父结点
         currentSum -= pTreeNode->m_nValue;
         path.pop_back();
     }

完整的测试程序

#include <iostream>
     #include <vector>
     #include <stdlib.h>
     
      using namespace std;
     
      struct BinaryTreeNode
     {
         int m_nValue;
         BinaryTreeNode * m_pLeft;
         BinaryTreeNode * m_pRight;
     };
     
      int count = 0;
     
      void findPath(BinaryTreeNode *pTreeNode,
             int expectedSum,
             vector<int>& path,
             int & currentSum)
     {
         if( !pTreeNode )
             return;
         currentSum += pTreeNode->m_nValue;
         path.push_back(pTreeNode->m_nValue);
         bool isLeaf = !(pTreeNode->m_pLeft) && !(pTreeNode->m_pRight);
         if(currentSum == expectedSum && isLeaf)
         {   
             vector<int>::iterator iter;
             for(iter = path.begin(); iter != path.end(); iter++)
             {   
                 cout << *iter << "\t";
             }   
             cout << endl;
         }   
         if(pTreeNode->m_pLeft)
             findPath(pTreeNode->m_pLeft, expectedSum, path, currentSum);
         if(pTreeNode->m_pRight)
             findPath(pTreeNode->m_pRight, expectedSum, path, currentSum);
     
         currentSum -= pTreeNode->m_nValue;
         path.pop_back();
     }
     
      void addTree(BinaryTreeNode **T, int num)
     {
         if(*T == NULL)
         {   
             *T = (BinaryTreeNode *)malloc(sizeof(BinaryTreeNode));
             (*T)->m_nValue = num;
             (*T)->m_pLeft = NULL;
             (*T)->m_pRight = NULL;
         }   
         else if((*T)->m_nValue > num)
              addTree(&((*T)->m_pLeft), num);
         else if((*T)->m_nValue < num)
             addTree(&((*T)->m_pRight), num);
         else
             cout << "重复加入同一结点" << endl;
     }
     
      int main()
     {
         BinaryTreeNode * T = NULL;
         addTree(&T, 10);
         addTree(&T, 12);
         addTree(&T, 5);
         addTree(&T, 7);
         addTree(&T, 4);
     
         vector<int> path;
         int sum = 0;
         findPath(T, 22, path, sum);
     
         return 0;
     }

**思路二**

另一种类似的方法不用录当前路径上所有元素的和sum，而是使用期望的和依次减去访问到的节点的值……最后是判断到达叶子节点时期望和是否减为0。

代码如下：

#include <iostream>
     #include <vector>
     #include <stdlib.h>
     
      using namespace std;
     
      struct BinaryTreeNode
     {
         int m_nValue;
         BinaryTreeNode * m_pLeft;
         BinaryTreeNode * m_pRight;
     };
     void FindPath(BinaryTreeNode *pNode,int sum,vector<int> &path);
     
      void addTree(BinaryTreeNode **T, int num)
     {
         if(*T == NULL)
         {   
             *T = (BinaryTreeNode *)malloc(sizeof(BinaryTreeNode));
             (*T)->m_nValue = num;
             (*T)->m_pLeft = NULL;
             (*T)->m_pRight = NULL;
         }   
         else if((*T)->m_nValue > num)
              addTree(&((*T)->m_pLeft), num);
         else if((*T)->m_nValue < num)
             addTree(&((*T)->m_pRight), num);
         else
             cout << "重复加入同一结点" << endl;
     }
     void FindPath(BinaryTreeNode *pNode,int sum,vector<int> &path)  
    {  
       //结点为空或值大于当前和  
        if(pNode == NULL || pNode->m_nValue > sum)  
            return;  
        path.push_back(pNode->m_nValue);  
       //判断是不是叶结点  
        bool isLeaf = (pNode->m_pLeft == NULL && pNode->m_pRight == NULL)? true: false;  
       //找到一条路径，打印  
        if(pNode->m_nValue == sum && isLeaf)  
      {  
            vector<int>::iterator iter = path.begin();  
            for(; iter != path.end(); iter++)  
                cout<<*iter<<' ';  
            cout<<endl;  
        }  
        else  
       {  
            //求剩余和  
            sum = sum - pNode->m_nValue;   
            //递归求解  
            FindPath(pNode->m_pLeft, sum, path);   
          FindPath(pNode->m_pRight, sum, path);  
       }  
        path.pop_back();  
    }  
    
      int main()
     {
         BinaryTreeNode * T = NULL;
         addTree(&T, 10);
         addTree(&T, 12);
         addTree(&T, 5);
         addTree(&T, 7);
         addTree(&T, 4);
     
         vector<int> path;
         int sum = 0;
         FindPath(T, 22, path);
     
         return 0;
     }