Binary Tree Path Sum

http://www.lintcode.com/en/problem/binary-tree-path-sum/

Discussion

An easy solution is based on the previous Binary Tree Path question. Record all the paths first, then output those paths whose sum is target.

要是这么简单就太没新意了，首先记录所有的paths会造成空间的浪费，通过计算累计sum，看是否为target，又会造成时间的浪费。先给出简单的solution，再看follow up。

//O(n*h) run time
//O(h + n) space
class Solution {
public:
    /**
     * @param root the root of binary tree
     * @param target an integer
     * @return all valid paths
     */
    vector<vector<int>> binaryTreePathSum(TreeNode *root, int target) {
        vector<vector<int> > all_paths;
        all_paths = binaryTreePathSumHelper(root);
        vector<vector<int> > result;
        for(int i=0; i<all_paths.size(); i++) {
            int sum = 0;
            for(auto const& n: all_paths[i]) {
                sum += n;
            }
            if(sum == target) {
                result.push_back(all_paths[i]);
            }
        }
        return result;
    }
    vector<vector<int>> binaryTreePathSumHelper(TreeNode *root) {
        vector<vector<int>> result;
        if(root == NULL) {
            return result;
        }
        vector<vector<int>> left = binaryTreePathSumHelper(root->left);
        vector<vector<int>> right = binaryTreePathSumHelper(root->right);
        if(left.empty() && right.empty()) {
            result.push_back({root->val});
            return result;
        }

        for(int i=0; i<left.size(); i++) {
            vector<int> ans = {root->val};
            ans.insert(ans.end(), left[i].begin(), left[i].end());
            result.push_back(ans);
        }

        for(int i=0; i<right.size(); i++) {
            vector<int> ans = {root->val};
            ans.insert(ans.end(), right[i].begin(), right[i].end());
            result.push_back(ans);
        }
    }
};

Follow up

DFS. 只输出valid path。

class Solution {
public:
    /**
     * @param root the root of binary tree
     * @param target an integer
     * @return all valid paths
     */
    vector<vector<int>> binaryTreePathSum(TreeNode *root, int target) {
        // Write your code here
        vector<vector<int>> result;
        if(root == NULL) return result;
        vector<TreeNode*> nodes;
        nodes.push_back(root);
        int path_sum = root->val;
        dfs(root, nodes, result, path_sum, target);
        return result;
    }
    void dfs(TreeNode *root, vector<TreeNode*> &path_nodes,
    vector<vector<int>> &records, int &path_sum, int target) {
        if(root == NULL) return;
        if(root->left == NULL && root->right == NULL) {//reches to a leaf, check if it is a valid path
            if(path_sum == target) {
                vector<int> ans;
                for(auto const& n: path_nodes) {
                    ans.push_back(n->val);
                }
                records.push_back(ans);
            }
        }

        if(root->left) {
            path_nodes.push_back(root->left);
            path_sum += root->left->val;
            dfs(root->left, path_nodes, records, path_sum, target);
            path_nodes.pop_back();
            path_sum -= root->left->val;
        }

        if(root->right) {
            path_nodes.push_back(root->right);
            path_sum += root->right->val;
            dfs(root->right, path_nodes, records, path_sum, target);
            path_nodes.pop_back();
            path_sum -= root->right->val;
        }
    }
};

更简洁的写法，gap取代sum和target.vector<TreeNode*> nodes;里面不用存TreeNode*，存int就可以了，因为不用节点地址在DFS的时候。

class Solution {
public:
    vector<vector<int>> pathSum(TreeNode* root, int sum) {
        vector<vector<int>> allpath;
        if(root == NULL) return allpath;
        vector<int> path = {root->val};
        dfsHelper(root, allpath, path, sum - root->val);
        return allpath;
    }
    void dfsHelper(TreeNode* root, vector<vector<int>> &allpath, vector<int> &path, int gap) {
        if(root == NULL) return;
        if(root->left== NULL && root->right==NULL && gap== 0) {
            allpath.emplace_back(path);
        }
        if(root->left != NULL) {
            path.emplace_back(root->left->val);
            dfsHelper(root->left, allpath, path, gap-root->left->val);
            path.pop_back();
        }
        if(root->right!= NULL) {
            path.emplace_back(root->right->val);
            dfsHelper(root->right, allpath, path, gap-root->right->val);
            path.pop_back();
        }
    }
};