Return the Path that Sum up to Target using DFS or BFS Algorithm

Time：2020-09-17 14:26:24
Class：Weblog
Read：25

Given a binary tree and a sum, find all root-to-leaf paths where each path’s sum equals the given sum. Note: A leaf is a node with no children.

Example:
Given the below binary tree and sum = 22,
      5
     / \
    4   8
   /   / \
  11  13  4
 /  \    / \
7    2  5   1
Return:
1
2
3
4
[
   [5,4,11,2],
   [5,8,4,5]
]
[
   [5,4,11,2],
   [5,8,4,5]
]

This is yet another classic tree puzzle that can be solved via either Depth First Search (DFS) or Breadth First Search (BFS) algorithm.

Breadth First Search Algorithm of Finding Path Sum

The BFS searches the tree level-by-level, via the use of a queue. A node in the tree contains three information: the current node, the path till this point, and the remaining sum.

When the remaining sum is zero and the node is a leaf, then we push the path to the result array. While the queue still has nodes, we pop one from the queue and push its children if any to the end of the queue.

If you are using Javascript, please note that you may need to clone the path array.

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} sum
 * @return {number[][]}
 */
var pathSum = function(root, sum) {
    var ans = [];
    if (!root) return [];
    var q = [[root, [], sum]];
    while (q.length) {
        var p = q.shift();
        var cur = p[0];
        var path = p[1];
        var sum = p[2];
        sum -= cur.val;
        path.push(cur.val);
        if ((sum === 0) && (cur.left === null) && (cur.right === null)) {
            ans.push(path);
        }
        if (cur.left) q.push([cur.left, path.slice(), sum]);
        if (cur.right) q.push([cur.right, path.slice(), sum]);
    }
    return ans;
};

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} sum
 * @return {number[][]}
 */
var pathSum = function(root, sum) {
    var ans = [];
    if (!root) return [];
    var q = [[root, [], sum]];
    while (q.length) {
        var p = q.shift();
        var cur = p[0];
        var path = p[1];
        var sum = p[2];
        sum -= cur.val;
        path.push(cur.val);
        if ((sum === 0) && (cur.left === null) && (cur.right === null)) {
            ans.push(path);
        }
        if (cur.left) q.push([cur.left, path.slice(), sum]);
        if (cur.right) q.push([cur.right, path.slice(), sum]);
    }
    return ans;
};

The following is a C++ implementation of the BFS algorithm where we use a std::tuple to store more than two information in a node. If there are two types of information, we can use std::pair instead.

/**
 * 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>> r;
        if (!root) return r;
        queue<tuple<TreeNode*, vector<int>, int>> Q;
        Q.push({root, {}, sum});
        while (!Q.empty()) {
            auto p = Q.front();
            Q.pop();
            TreeNode* cur = std::get<0>(p);
            vector<int> path = std::get<1>(p);
            int curSum = std::get<2>(p);
            curSum -= cur->val;
            path.push_back(cur->val);
            if (curSum == 0) {
                if ((cur->left == nullptr) && (cur->right == nullptr)) {
                    r.push_back(path);
                }
            } 
            if (cur->left != nullptr) Q.push({cur->left, path, curSum});
            if (cur->right != nullptr) Q.push({cur->right, path, curSum});
        }
        return r;
    }
};

/**
 * 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>> r;
        if (!root) return r;
        queue<tuple<TreeNode*, vector<int>, int>> Q;
        Q.push({root, {}, sum});
        while (!Q.empty()) {
            auto p = Q.front();
            Q.pop();
            TreeNode* cur = std::get<0>(p);
            vector<int> path = std::get<1>(p);
            int curSum = std::get<2>(p);
            curSum -= cur->val;
            path.push_back(cur->val);
            if (curSum == 0) {
                if ((cur->left == nullptr) && (cur->right == nullptr)) {
                    r.push_back(path);
                }
            } 
            if (cur->left != nullptr) Q.push({cur->left, path, curSum});
            if (cur->right != nullptr) Q.push({cur->right, path, curSum});
        }
        return r;
    }
};

Depth First Search Algorithm of Finding Path Sum

The DFS often finds a path quicker than the BFS. And a DFS is often implemented as a recursion. See below local recursive function dfs in Javascript solution.

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} sum
 * @return {number[][]}
 */
var pathSum = function(root, sum) {
    var ans = [];
    function dfs(root, arr, s) {
        if (!root) return;
        arr.push(root.val);
        s -= root.val;
        if ((s === 0) && (root.left === null) && (root.right === null)) {
            ans.push(arr);
            return;
        }
        if (root.left) dfs(root.left, arr.slice(), s);
        if (root.right) dfs(root.right, arr.slice(), s);
    }
    dfs(root, [], sum);
    return ans;
};

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} sum
 * @return {number[][]}
 */
var pathSum = function(root, sum) {
    var ans = [];
    function dfs(root, arr, s) {
        if (!root) return;
        arr.push(root.val);
        s -= root.val;
        if ((s === 0) && (root.left === null) && (root.right === null)) {
            ans.push(arr);
            return;
        }
        if (root.left) dfs(root.left, arr.slice(), s);
        if (root.right) dfs(root.right, arr.slice(), s);
    }
    dfs(root, [], sum);
    return ans;
};

Similarly, the C++ DFS implementation is done via recursion.

/**
 * 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>> r;
        dfs(r, {}, root, sum);
        return r;
    }
    
private:
    void dfs(vector<vector<int>> &r, vector<int> cur, TreeNode* root, int sum) {
        if (root == nullptr) return;
        sum -= root->val;
        cur.push_back(root->val);
        if ((sum == 0) && (root->left == nullptr) && (root->right == nullptr)) {
            r.push_back(cur);
        } else {
            dfs(r, cur, root->left, sum);
            dfs(r, cur, root->right, sum);            
        }
    }
};

/**
 * 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>> r;
        dfs(r, {}, root, sum);
        return r;
    }
    
private:
    void dfs(vector<vector<int>> &r, vector<int> cur, TreeNode* root, int sum) {
        if (root == nullptr) return;
        sum -= root->val;
        cur.push_back(root->val);
        if ((sum == 0) && (root->left == nullptr) && (root->right == nullptr)) {
            r.push_back(cur);
        } else {
            dfs(r, cur, root->left, sum);
            dfs(r, cur, root->right, sum);            
        }
    }
};

All four implementations run at O(N) time and O(N) space, where N is the number of nodes in the tree.

–EOF (The Ultimate Computing & Technology Blog) —

Recommend：
7 Ways To Take Advantage of 404 Error Pages
7 Ways to Enhance Your Blog with Video Advertising
California Consumer Privacy Act (CCPA) Compliance Guide For AdSe
What Is WordPress Live Chat and How Do You Implement It?
5 Beginner’s Tips to Building a WordPress Blog
8 Best Affiliate Marketing Plugins For Your Blog
How Many Squares/Rectangles Does a Rubik Cube Have?
Find the 10001st Prime Number
The Difference Between Sum of Squares and Square of the Sum
Number of Steps to Reduce a Number in Binary Representation to O

Comment list

Comment add: Name：　Check：