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

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

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

推荐阅读：
食疗：有效增强男人性能力的八款药膳　 枸杞保健食疗功效多补肾益精养肝明目　 如何从感官上辨别枸杞的真假和质量优劣　 红酒对人体有保健作用但并非人人适宜　 食品安全：盘点有毒的11种常见食物　 鸡蛋的蛋黄和蛋清到底哪个更有营养？　 揭秘减肥食品菇类营养价值抗癌降血脂　 冬季感冒多喝姜茶可治疗外感风寒感冒　 消除身体疲劳可多吃七种带“香”的食物　 饮食与健康：维生素B2的补充无需刻意　
评论列表
添加评论