My cpp solution 【Path Sum II】 with notes


  • 0
    X
    /**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution {
    public:
        vector<vector<int>> pathSum(TreeNode* root, int sum) {
    			vector<vector<int> > ret;
    			// Terminal conditon 1 : to the null (not leaf node)
    			// even if sum equals zero at the time, becasue not leaf node
    			// so it is also not the available solution path
    			if (!root) return ret;
    			// Terminal condition 2 : leaf node
    			if ( !root->left && !root->right )
    			{
    				// if leaf node's val equal sum
    				if ( sum==root->val )
    				{
    					vector<int> tmp;
    					tmp.insert(tmp.begin(),root->val);
    					ret.push_back(tmp);
    				}
    				return ret;
    			}
    			// not leaf node : move forward to left and right
    			vector<vector<int> > l = Solution::pathSum(root->left, sum - root->val);
    			vector<vector<int> > r = Solution::pathSum(root->right, sum - root->val);
    			for ( size_t i = 0; i<l.size(); ++i )
    			{
    				l[i].insert(l[i].begin(), root->val);
    				ret.push_back(l[i]);
    			}
    			for ( size_t i = 0; i<r.size(); ++i )
    			{
    				r[i].insert(r[i].begin(), root->val);
    				ret.push_back(r[i]);
    			}
    			return ret;
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.