首页 > 其他 > 详细

二叉树中和为某个值得路径

时间:2018-04-07 00:27:37      阅读:250      评论:0      收藏:0      [点我收藏+]

题目描述

输入一颗二叉树和一个整数,打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。
实现:
class Solution {
        vector<int> in ;
        vector<vector<int>> out ;
public:
    vector<vector<int> > FindPath(TreeNode* root,int expectNumber) {
        if(!root)
            return out;
        in.push_back(root->val);
        if(root->left == 0 && root->right == 0 && root->val == expectNumber)
        {
            out.push_back(in);
        }    
        if(root->left)
        {
            FindPath(root->left,expectNumber - root->val);
            if(!in.empty())
                in.pop_back();
         }   
        if(root->right)
        {
            FindPath(root->right,expectNumber - root->val);
            if(!in.empty())
                in.pop_back();
        }
        return out;
     }
};

样例做法:

class Solution {
        vector<int> in ;
        vector<vector<int>> out ;
public:
    vector<vector<int> > FindPath(TreeNode* root,int expectNumber) {
        if(!root)
            return out;
        in.push_back(root->val);
        if(root->left == 0 && root->right == 0 && root->val == expectNumber)
        {
            out.push_back(in);
        }    
        if(root->left)
        {
            FindPath(root->left,expectNumber - root->val);
         }   
        if(root->right)
        {
            FindPath(root->right,expectNumber - root->val);
        }
        if(!in.empty())
            in.pop_back();
        return out;
     }
};

本来还以为样例不对,

    3

  5    8

2  6  7  9

本来认为5为根时遍历完左右没有弹出5,后来终于想通,忘记了以5为根时后面还会走if弹出。

二叉树中和为某个值得路径

原文:https://www.cnblogs.com/Lune-Qiu/p/8729296.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!