首页 > 剑指offer > 剑指offer(18)-二叉树中和为某一值的路径[数据结构]九度1368
2014
02-24

剑指offer(18)-二叉树中和为某一值的路径[数据结构]九度1368

题目来自九度剑指offer系列

题目描述:
输入一颗二叉树和一个整数,打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。 
输入:
每个测试案例包括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:

面试题中经常会遇到关于二叉树的问题。基本思路一般就是递归,深搜。这一题其实也是这样,没有太特别的。

详细思路:http://www.acmerblog.com/interview-4-1937.html

下面的代码有两个技巧:1) 由于是按字典序输出,可以让左孩子的值是总是小的。先序遍历就行了。

2) 存储路径,其实是类似栈,函数结束要弹出。

//============================================================================
// Name        : 二叉树和.cpp
// Author      : coder
// Version     :
// Copyright   : www.acmerblog.com
// Description : Hello World in C++, Ansi-style
//============================================================================
#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
int n,k,b,c;
struct Tree{
    int l, r;
    int data;
};
Tree tree[10010];
int path[10010],cnt;//存储路径
void find(int index,int sum){
    if(index != -1){
        Tree t = tree[index];
        sum += t.data;
        path[cnt++] = index; //存入当前节点的编号
        if(sum == k && tree[index].l==-1 && tree[index].r == -1){
            printf("A path is found:");
            for(int j=0; j<cnt; j++) printf(" %d",path[j]);
            puts("");
            cnt--;
            return;
        }else if(sum > k){
            cnt--;
            return;
        }
        find(t.l,sum);
        find(t.r,sum);
        cnt--; //函数返回时记得弹出当前的节点
    }
}
int main() {
    while(scanf("%d%d", &n, &k) != EOF){
        cnt = 0;
        for(int i=1; i<=n; i++){
            scanf("%d%d%d", &tree[i].data, &b, &c);
            if(b > c) swap(b ,c);//保证字典序
            tree[i].l = b;
            tree[i].r = c;
        }
        puts("result:");
        find(1,0);
    }
    return 0;
}
/**************************************************************
    Problem: 1368
    User: 从此醉
    Language: C++
    Result: Accepted
    Time:40 ms
    Memory:1676 kb
****************************************************************/

ACM之家原创,链接:http://www.acmerblog.com/interview-offer18-jiudu-1368-4585.html


  1. #include <stdio.h>
    int main(void)
    {
    int arr[] = {10,20,30,40,50,60};
    int *p=arr;
    printf("%d,%d,",*p++,*++p);
    printf("%d,%d,%d",*p,*p++,*++p);
    return 0;
    }

    为什么是 20,20,50,40,50. 我觉得的应该是 20,20,40,40,50 . 谁能解释下?

  2. 站长好。我是一个准备创业的互联网小白,我们打算做一个有关国*际*游*学的平台。手上也有了一些境外资源。现阶段的团队现在没有cto.原意出让一些管理股寻找一个靠谱的技术专家做合伙人, 不知道是不是能得到您的帮助。发个帖子或者其他方式。期待您的回应。可以加我微信tianxielemon聊聊。