设为首页 加入收藏

TOP

通过二叉树和一个数找到路径
2013-11-20 14:24:16 来源: 作者: 【 】 浏览:132
Tags:通过 一个数 找到 路径

    Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.
    For example:
    Given the below binary tree and sum = 22,
    5
    / \
    4   8
    /   / \
    11  13  4
    /  \    / \
    7    2  5   1
    return
    [
    [5,4,11,2],
    [5,8,4,5]
    ]
    问题描述:给定一个二叉树和一个数,找到在这个二叉树中从根节点到叶子节点路径和等于这个数字的所有路径。
    前面多次提到,与二叉树相关的问题,多半都可以用递归。
    对于本题而言,vector<vector<int> > pathSum(TreeNode *root, int sum)函数返回以root为根的路径和等于sum的所有路径,那么可以这么想
    pathSum(root->left, sum-(root->val))返回左子树中和为sum-(root->val)的所有路径,
    pathSum(root->right, sum-(root->val))返回右子树中和为sum-(root->val)的所有路径,
    那么pathSum(root, sum)可以通过将root->val加入到上面所有路径中,然后将左右子树的路径进行合并得到。
    然后再判断临界条件即可。
    class Solution {
    public:
    vector<vector<int> > pathSum(TreeNode *root, int sum) {
    // IMPORTANT: Please reset any member data you declared, as
    // the same Solution instance will be reused for each test case.
    if(root == NULL)
    return vector<vector<int> >();
    if(root->left == NULL && root->right == NULL && root->val == sum) {
    vector<vector<int> > vec;
    vector<int> ivec;
    ivec.push_back(sum);
    vec.push_back(ivec);
    return vec;
    }
    vector<vector<int> > vec1 = pathSum(root->left, sum-(root->val));
    vector<vector<int> > vec2 = pathSum(root->right, sum-(root->val));
    for(vector<vector<int> >::iterator iter = vec1.begin();
    iter != vec1.end(); ++iter) {
    (*iter)。insert((*iter)。begin(), root->val);
    }
    for(vector<vector<int> >::iterator iter = vec2.begin();
    iter != vec2.end(); ++iter) {
    (*iter)。insert((*iter)。begin(), root->val);
    vec1.push_back(*iter);
    }
    return vec1;
    }
    };

】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
分享到: 
上一篇顺序队列 Queue 下一篇前序遍历二叉树递归解法

评论

帐  号: 密码: (新用户注册)
验 证 码:
表  情:
内  容:

·Redis 分布式锁全解 (2025-12-25 17:19:51)
·SpringBoot 整合 Red (2025-12-25 17:19:48)
·MongoDB 索引 - 菜鸟 (2025-12-25 17:19:45)
·What Is Linux (2025-12-25 16:57:17)
·Linux小白必备:超全 (2025-12-25 16:57:14)