首页 > 代码库 > Path Sum II

Path Sum II

2024-07-17 23:18:38   218人阅读

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]]

思路：对二叉树进行遍历即可。

class Solution {public:    vector<vector<int>> pathSum( TreeNode *root, int sum ) {        vector<int> path;        PathSumSub( path, root, sum );        return pathes;    }private:    void PathSumSub( vector<int>& path, TreeNode *node, int sum ) {        if( !node ) { return; }        path.push_back( node->val );        sum -= node->val;        if( !node->left && !node->right ) {            if( sum == 0 ) { pathes.push_back( path ); }            path.pop_back();            return;        }        if( node->left ) { PathSumSub( path, node->left, sum ); }        if( node->right ) { PathSumSub( path, node->right, sum ); }        path.pop_back();    }    vector<vector<int>> pathes;};

 


联系
我们