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

  • 时间：2020-09-17 14:26:24
  • 分类：网络文摘
  • 阅读：130 次

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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

/**
 * 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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

/**
 * 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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

/**
 * 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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

/**
 * 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) —

推荐阅读：
数学题:妈妈买苹果和梨各用去多少钱？　 求年利率的数学题　 丝瓜菌菇鸡蛋汤营养美味之夏季消暑佳品　 数学题：王老师平均每月要付给银行多少利息　 数学题：一列火车通过250米长的道路用25秒　 数学题：三角形的左、右两条边分别被六等分、五等分　 龙湖作文　 调研之旅　 我的最后一个儿童节作文400字　 家乡的龙湖作文　
评论列表
添加评论