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

符号 阅读:355 2020-10-21 17:21:32 评论:0

题目描述

输入一颗二叉树的根节点和一个整数,打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。
 
解:这题其实有限制条件,但是没看出来。就是要从根节点一直到叶子节点,全部的和。中间的节点不会断层,其实就是深度优先遍历的类型
/* 
struct TreeNode { 
    int val; 
    struct TreeNode *left; 
    struct TreeNode *right; 
    TreeNode(int x) : 
            val(x), left(NULL), right(NULL) { 
    } 
};*/ 
class Solution { 
public: 
    void ResFindPath(vector<vector<int> >&vec_vec,vector<int>vec,TreeNode* root,int expectNumber) 
    { 
 
        if(root==nullptr) 
        { 
            return; 
        } 
                //不计算本节点值 
        //ResFindPath(vec_vec,vec,root->right,expectNumber); 
        //ResFindPath(vec_vec,vec,root->right,expectNumber); 
         
        //计算本节点值 
        vec.emplace_back(root->val); 
        if(expectNumber-root->val==0&&(root->left==nullptr&&root->right==nullptr)) 
        { 
            vec_vec.emplace_back(vec); 
            return; 
        } 
        ResFindPath(vec_vec,vec,root->left,expectNumber-root->val); 
        ResFindPath(vec_vec,vec,root->right,expectNumber-root->val); 
    } 
    vector<vector<int> > FindPath(TreeNode* root,int expectNumber) { 
        vector<vector<int> > vec_vec_ret; 
        vector<int> vec; 
        ResFindPath(vec_vec_ret,vec,root,expectNumber); 
        return vec_vec_ret; 
    } 
};

 

声明

1.本站遵循行业规范,任何转载的稿件都会明确标注作者和来源;2.本站的原创文章,请转载时务必注明文章作者和来源,不尊重原创的行为我们将追究责任;3.作者投稿可能会经我们编辑修改或补充。

发表评论
搜索
排行榜
KIKK导航

KIKK导航

关注我们