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

Posted on One min read

1. 描述

输入一棵二叉树和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。

2. 提示

  • 节点总数 <= 10000

3. 题解

n 是 i_root 中的节点数目
时间复杂度: O(n)
空间复杂度: O(n)

class Solution 
{
private:
    vector<vector<int>> paths;

    void getPaths(TreeNode *i_root, vector<int> &m_path, int target)
    {
        target -= i_root->val;
        m_path.push_back(i_root->val);

        if(!i_root->left && !i_root->right && target == 0) 
            paths.push_back(m_path);

        if(i_root->left) getPaths(i_root->left, m_path, target);
        if(i_root->right) getPaths(i_root->right, m_path, target);

        m_path.pop_back();
        target += i_root->val;
    }
public:
    // vector<vector<int>> pathSum(TreeNode* root, int sum)
    vector<vector<int>> pathSum(TreeNode *i_root, int target) 
    {
        if(i_root)
        {
            vector<int> path;
            getPaths(i_root, path, target);
        }
        
        return paths;
    }
};
comments powered by Disqus