二叉树中和为某一值的路径

曾经终败给现在 2022-03-20 02:50 153阅读 0赞

**何海涛：《剑指Offer：名企面试官精讲典型编程题》：九度OJ**

**题目描述：[http://ac.jobdu.com/problem.php?cid=1039&pid=10][http_ac.jobdu.com_problem.php_cid_1039_pid_10]**

输入一颗二叉树和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。

**输入：**

每个测试案例包括n+1行：

第一行为2个整数n，k(1<=n<=10000)，n表示结点的个数，k表示要求的路径和，结点编号从1到n。

接下来有n行。这n行中每行为3个整数vi,leftnode,rightnode，vi表示第i个结点的值，leftnode表示第i个结点的左孩子结点编号，rightnode表示第i个结点的右孩子结点编号，若无结点值为-1。编号为1的结点为根结点。

**输出：**

对应每个测试案例，先输出“result:”占一行，接下来按字典顺序输出满足条件的所有路径，这些路径由结点编号组成，输出格式参照输出样例。

**样例输入：**

5 22

10 2 3

5 4 5

12 -1 -1

4 -1 -1

7 -1 -1

1 5

1 -1 -1

**样例输出：**

result:

A path is found: 1 2 5

A path is found: 1 3

result:

代码AC：

思想：遍历树知道叶子，用栈保存路径，类似于迷宫问题！

#include <stdio.h>
    #include <stdlib.h>
    
    typedef struct tree
    {
            int id;
            int vi;
            int lc;
            int rc;
    }tree, *p_tree;
    
    int *stack;
    int n, k;
    int top = -1;
    p_tree t;
    
    void fun( int idx, int s )
    {
         int tmp;
         
         s += t[idx].vi;
         
         if( t[idx].lc == -1 && t[idx].rc == -1 )
         {
             if( s == k )
             {
                 printf("A path is found: ");
                 tmp = 0;
                 while( tmp <= top )
                 {
                        printf("%d ", stack[tmp++]);
                 }
                 printf("%d\n", t[idx].id);
             }
         }
         else
         {
             stack[++top] = t[idx].id;
             
             if( t[idx].lc < t[idx].rc )   //
             {
                 if( t[idx].lc <= n && t[idx].lc >= 1 )
                 {
                     fun( t[idx].lc - 1, s );
                 }
             
                 if( t[idx].rc <= n && t[idx].rc >= 1 )
                 {
                     fun( t[idx].rc - 1, s );
                 }
             }
             else
             {
                 if( t[idx].rc <= n && t[idx].rc >= 1 )
                 {
                     fun( t[idx].rc - 1, s );
                 }
             
                 if( t[idx].lc <= n && t[idx].lc >= 1 )
                 {
                     fun( t[idx].lc - 1, s );
                 }
             }
             
    
             
             top--;
         }
    }
    
    int main()
    {
        int i;
        
        while( scanf("%d%d", &n, &k) != EOF )
        {
               t = ( p_tree )malloc( sizeof( tree ) * n );
               stack = ( int* )malloc( sizeof( int ) * n );
               
               for( i = 0; i < n; i++ )
               {
                    t[i].id = i + 1;
                    scanf("%d%d%d", &t[i].vi, &t[i].lc, &t[i].rc);
               } 
               
               printf("result:\n");
               
               fun( 0, 0 );
        }
        
        return 0;
    }

[http_ac.jobdu.com_problem.php_cid_1039_pid_10]: http://ac.jobdu.com/problem.php?cid=1039&pid=10