求二叉树中和为给定值的所有路径

转自:http://blog.csdn.net/lalor/article/details/7614381

问题定义:

You are given a binary tree in which each node contains a value. Design an algorithm to print all paths which sum up to that value. Note that it can be any path in the tree-it does not have to start at the root.

解题思路:

一层一层的遍历,保存当前节点到根节点的完整路径,然后从当前节点向上扫描,如果找到了当前节点到某个节点的和等于给定值,则输出之。程序对每个节点都需要遍历一遍,还要扫描当前节点到根节点的路径,且需要保存每个节点到根节点的路径,所以时间复杂度为O(nlgn),空间复杂度为O(nlgn)。(ps:关于本程序中建树部分,可以参考:http://blog.csdn.net/lalor/article/details/7613621

代码实例:

#include <algorithm>
#include <iostream>
#include <time.h>
#include <assert.h>
#include <stdio.h>
#include <vector>  

using namespace std;  

struct node
{
    int data;
    struct node * lchild;
    struct node * rchild;
};  

//将数组转换为深度最低的二叉树,采用了二分查找的思想
struct node* ConvertArrayToTree(int data[], int first, int last)
{
    if (last < first)
    {
        return NULL;
    }
    else
    {
        int mid = ( last + first ) / 2;
        struct node * newNode = NULL;
        newNode = (struct node *)malloc(sizeof(struct node));
        newNode->data = data[mid];
        newNode->lchild = ConvertArrayToTree(data, first, mid - 1);
        newNode->rchild = ConvertArrayToTree(data, mid + 1, last);
        return newNode;
    }
}  

//再最左边插入一个节点
void InsertNodeAtLeft(struct node *root, struct node *newNode)
{
    assert(root != NULL && newNode != NULL);
    while(root->lchild != NULL)
    {
        root = root->lchild;
    }
    root->lchild = newNode;
}  

//在最右边插入一个节点
void InsertNodeAtRight(struct node *root, struct node *newNode)
{
    assert(root != NULL && newNode != NULL);
    while(root->rchild != NULL)
    {
        root = root->rchild;
    }
    root->rchild = newNode;
}
//中序遍历
void Traverse(struct node *root)
{
    if (root == NULL)
    {
        return;
    }
    Traverse(root->lchild);
    Traverse(root->rchild);
    printf("%d\t", root->data);
}  

//打印和为sum的路径
void print(vector<int>& buffer, int first, int last)
{
    int i;
    for (i = first; i <= last; i++)
    {
        cout << buffer[i] << "\t";
    }
    cout << endl;
}
void findSum(struct node *head, int sum, vector<int> &buffer, int level)
{
    if (head == NULL) return;  

    int i;
    int tmp = sum;
    buffer.push_back(head->data);
    for (i = level; i >= 0; i--)
    {
        tmp -= buffer[i];
        if (tmp == 0) print(buffer, i, level);
    }  

    vector<int> lbuffer(buffer);
    vector<int> rbuffer(buffer);  

    findSum(head->lchild, sum, lbuffer, level + 1);
    findSum(head->rchild, sum, rbuffer, level + 1);
}  

int main(int argc, char* argv[])
{
    const int SIZE = 10;//测试的数据量
    int data[SIZE];//保存数据
    int i, j;
    struct node *head = NULL;  

    for (i = 0; i < SIZE; i++)
    {
        data[i] = i + 1;
    }  

    head = ConvertArrayToTree(data, 0, SIZE - 1);  

    struct node *one = (struct node *)malloc(sizeof(struct node));
    struct node *two = (struct node *)malloc(sizeof(struct node));
    one->data = 11;
    one->lchild = NULL;
    one->rchild = NULL;  

    two->data = 4;
    two->lchild = NULL;
    two->rchild = NULL;  

    InsertNodeAtLeft(head, one);
    InsertNodeAtRight(head, two);
    //遍历数据
//  Traverse(head);
//  printf("\n");
    vector<int> v;
    findSum(head, 14, v, 0);
    return 0;
} 

该示例中所使用的二叉树如下所示:

运行结果如下:

时间: 08-23

求二叉树中和为给定值的所有路径的相关文章

求数组中和为给定值的任意两个数

转载请注明出处:http://blog.csdn.net/ns_code/article/details/24933341     题目: 输入一个已经按升序排序过的数组和一个数字,在数组中查找两个数,使得它们的和正好是输入的那个数字.要求时间复杂度是O(n).如果有多对数字的和等于输入的数字,输出任意一对即可. 例如输入数组1.2.4.7.11.15和数字15.由于4+11=15,因此输出4和11.     思路: 最直接的做法是暴力法,两个for循环,时间复杂度为O(n*n),但是这样没有充

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

输入一个二叉树,查找该树的所有路径(从根结点到叶结点的通路),并返回和(路径上所有结点值的和)为某一指定值的路径. 1 /////////////二叉树中和为某一值的路径///////////////////// 2 void FindPath(BinaryTreeNode* pRoot ,int expectedSum ,vector<int>& path ,int currentSum) 3 { 4 if (pRoot == NULL) 5 { 6 return; 7 } 8 cu

二叉树中和为某一值的路径-剑指Offer

二叉树中和为某一值的路径 题目描述 输入一颗二叉树和一个整数,打印出二叉树中结点值的和为输入整数的所有路径.路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径. 思路 用栈来存储二叉树的路径,遍历到叶子结点就判断是否总和为target,是的话打印,若不是叶子结点,那继续遍历左右子树 注意:打印完后返回父结点时要弹出栈顶的叶子结点,并且总和减去该值 注意:打印路径时要遍历栈 代码 import java.util.ArrayList; import java.util.Stack;

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

二叉树中和为某一值的路径 参与人数:2929时间限制:1秒空间限制:32768K 算法知识视频讲解 题目描述 输入一颗二叉树和一个整数,打印出二叉树中结点值的和为输入整数的所有路径.路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径. 牛客网不给测试用例让我感到很迷惑啊..再次提醒自己,vector是否为空用vector.empty()判断! // 24.cpp : 定义控制台应用程序的入口点. // #include "stdafx.h" #include <v

LeetCode | 面试题34. 二叉树中和为某一值的路径【剑指Offer】【Python】

LeetCode 面试题34. 二叉树中和为某一值的路径[剑指Offer][Medium][Python][回溯] 问题 力扣 输入一棵二叉树和一个整数,打印出二叉树中节点值的和为输入整数的所有路径.从树的根节点开始往下一直到叶节点所经过的节点形成一条路径. 示例: 给定如下二叉树,以及目标和 sum = 22, 5 / 4 8 / / 11 13 4 / \ / 7 2 5 1 返回: [ [5,4,11,2], [5,8,4,5] ] 提示: 节点总数 <= 10000 注意:本题与主站 1

求数组中和为给定值的所有子序列

2017年网易游戏的一道编程题,大致意思是满足组合攻击技能,必须是所选择时技能的和为m(m>0),且所选的这些技能的乘积最大: 分解后主解决两个问题: 其一:求数组中和为m的所有子数组: 其二:在满足一的条件下,求所有子数组的最大值: 主要考察的还是如何求数组中和为m的所有子数组: 如:数组[1,2,3,4,5,6],m=7时,满足条件的子数组有[1,2,4],[3,4],[2,5],[1,6]; 主要使用回溯法解决该问题,思路以后补上: import java.util.ArrayList;

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

0 引言 题目:输入一颗二叉树的根节点和一个整数,打印出二叉树中结点值的和为输入整数的所有路径.路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径.(注意: 在返回值的list中,数组长度大的数组靠前) 1 抽象问题具体化 举例1:树的形态如图所示.给定的整数值为22,求路径. 解答:所有的路径总共有三条,分别是 1)10->5->4,和为19: 2)10->5->7,和为22: 3)10->12,和为22. 2 具体问题抽象分析 分三步 1)写出所有的路径:

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

输入一个二叉树和一个整数,打印出二叉树中结点值的和为输入整数的所有路径.从树的根结点开始往下一直到叶结点所经过的结点形成一条路径. 如上图的二叉树,当输入根结点和一个数值12的时候,就有两条路径"1->2->4->5"和"1->3->8",如果存在,就输出上述路径,如果没有任何一条路径满足就不输出路径并提示: 首先,路径一定是从根结点开始到某个叶子结点结束,这才是一条路径,因此,应该最先访问的就是根结点,而在二叉树的先中后序遍历中只有先

【剑指Offer】二叉树中和为某一值的路径

问题描述 输入一颗二叉树和一个整数,打印出二叉树中结点值的和为输入整数的所有路径.路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径. 算法分析 如果 root 等于 输入数,将root放在返回数组里返回:如果root大于输入数,返回空值: 如果root小于输入数,将root放在数组里,输入数自减root,一同随root的子树递归: 如果输入数为0了且左右子树都为空,即为叶子节点,则这条路径可行,返回数组: 如果 root 没有子树了,同时输入数还没为0,说明此路不通,返回NUL