给定一棵二叉树，每个结点包含一个值。打印出所有满足以下条件的路径：路径上结点的值加起来等于给定的一个值。注意：这些路径不必从根结点开始。...-白红宇

给定一棵二叉树，每个结点包含一个值。打印出所有满足以下条件的路径：路径上结点的值加起来等于给定的一个值。注意：这些路径不必从根结点开始。...

阅读量：6087 次

发布时间：2019-06-20

本文共 2987 字，大约阅读时间需要 9 分钟。

给定一棵二叉树，每个结点包含一个值。打印出所有满足以下条件的路径：路径上结点的值加起来等于给定的一个值。注意：这些路径不必从根结点开始。

解答

方案1：如果结点中包含指向父亲结点的指针，那么，只需要去遍历这棵二叉树，然后从每个结点开始，不断地去累加上它父亲结点的值直到父亲结点为空(这个具有唯一性，因为每个结点都只有一个父亲结点。也正因为这个唯一性，可以不另外开额外的空间来保存路径)，如果等于给定的值sum，则打印输出。

代码如下：

void find_sum(Node* head, int sum){
          if(head == NULL) return;    Node *no = head;    int tmp = 0;    for(int i=1; no!=NULL; ++i){
              tmp += no->key;        if(tmp == sum)            print(head, i);        no = no->parent;    }    find_sum(head->lchild, sum);    find_sum(head->rchild, sum);}

打印输出时，只需要提供当前结点的指针，及累加的层数即可。然后从当前结点开始，不断保存其父亲结点的值(包含当前结点)直到达到累加层数，然后逆序输出即可。

代码如下：

void print(Node* head, int level){
          vector
     
       v;    for(int i=0; i
      
       key);        head = head->parent;    }    while(!v.empty()){
              cout<
       
        <<" ";        v.pop_back();    }    cout<

方案2：如果结点中不包含指向父亲结点的指针，则在二叉树从上向下查找路径的过程中，需要为每一次的路径保存中间结果，累加求和仍然是从下至上的，对应到保存路径的数组，即是从数组的后面开始累加的，这样能保证遍历到每一条路径。

代码如下：

void print2(vector
     
       v, int level){
          for(int i=level; i

v, int level){

if(head == NULL) return; v.push_back(head->key); int tmp = 0; for(int i=level; i>-1; --i){

tmp += v.at(i); if(tmp == sum) print2(v, i); } vector

v1(v), v2(v); find_sum2(head->lchild, sum, v1, level+1); find_sum2(head->rchild, sum, v2, level+1);}

方案1和方案2的本质思想其实是一样的，不同的只是有无指向父亲结点的指针这个信息。如果没有这个信息，则需要增加许多额外的空间来存储中间信息。

注意：方案1和方案2代码中的level并非指同一概念，方案1中level表示层数，最小值为1；方案2中level表示第几层，最小值为0。

完整代码如下：

#include 
     
      #include 
      
       #include 
       
        using namespace std;const int maxn = 100;struct Node{
          int key;    Node *lchild, *rchild, *parent;};Node node[maxn];int cnt;void init(){
          memset(node, '\0', sizeof(node));    cnt = 0;}void create_minimal_tree(Node* &head, Node *parent, int a[], int start, int end){
          if(start <= end){
              int mid = (start + end)>>1;        node[cnt].key = a[mid];        node[cnt].parent = parent;        head = &node[cnt++];        create_minimal_tree(head->lchild, head, a, start, mid-1);        create_minimal_tree(head->rchild, head, a, mid+1, end);    }}void print(Node* head, int level){
          vector
        
          v;    for(int i=0; i
         
          key);        head = head->parent;    }    while(!v.empty()){
              cout<
          
           <<" "; v.pop_back(); } cout<
           
            key; if(tmp == sum) print(head, i); no = no->parent; } find_sum(head->lchild, sum); find_sum(head->rchild, sum);}void print2(vector
            
              v, int level){ for(int i=level; i

v, int level){ if(head == NULL) return; v.push_back(head->key); int tmp = 0; for(int i=level; i>-1; --i){ tmp += v.at(i); if(tmp == sum) print2(v, i); } vector

v1(v), v2(v); find_sum2(head->lchild, sum, v1, level+1); find_sum2(head->rchild, sum, v2, level+1);}int main(){ init(); int a[] = { 4, 3, 8, 5, 2, 1, 6 }; Node *head = NULL; create_minimal_tree(head, NULL, a, 0, 6); // find_sum(head, 8); vector

v; find_sum2(head, 8, v, 0); return 0;}

转载地址：http://sppwa.baihongyu.com/