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

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

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：
6 Simple Ways to Promote Your Blog
The Secret to Writing More Compelling Blog Titles
5 Habits Of Highly Successful Bloggers
5 Ways to Connect Your Blog Content Writers
Google’s Perfect World: A New Technical SEO Framework
Boost the Visibility of Your Blog With In-Person Events
Are Top 20 Witnesses Voting Each Other? Introducing Witness-voti
How to Design a Browser History using Double-ended Queue (deque)
SteemJs: How Many Witnesses are Running on 23.1?
Illustrating the Blockchain via SteemJs – Blocks are Chain

Comment list

Comment add: Name：　Check：