437 Path Sum III 路徑總和 III

Description:
You are given a binary tree in which each node contains an integer value.

Find the number of paths that sum to a given value.

The path does not need to start or end at the root or a leaf, but it must go downwards (traveling only from parent nodes to child nodes).

The tree has no more than 1,000 nodes and the values are in the range -1,000,000 to 1,000,000.

Example:

root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8

      10
     /  \
    5   -3
   / \    \
  3   2   11
 / \   \
3  -2   1

Return 3. The paths that sum to 8 are:

1.  5 -> 3
2.  5 -> 2 -> 1
3. -3 -> 11

題目描述:
給定一個(gè)二叉樹，它的每個(gè)結(jié)點(diǎn)都存放著一個(gè)整數(shù)值。

找出路徑和等于給定數(shù)值的路徑總數(shù)。

路徑不需要從根節(jié)點(diǎn)開始，也不需要在葉子節(jié)點(diǎn)結(jié)束，但是路徑方向必須是向下的（只能從父節(jié)點(diǎn)到子節(jié)點(diǎn)）。

二叉樹不超過1000個(gè)節(jié)點(diǎn)，且節(jié)點(diǎn)數(shù)值范圍是 [-1000000,1000000] 的整數(shù)。

示例：

root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8

      10
     /  \
    5   -3
   / \    \
  3   2   11
 / \   \
3  -2   1

返回 3。和等于 8 的路徑有:

1.  5 -> 3
2.  5 -> 2 -> 1
3.  -3 -> 11

思路:

1. 深度優(yōu)先搜索和層次遍歷結(jié)合
2. 雙重遞歸
   時(shí)間復(fù)雜度O(n ^ 2), 空間復(fù)雜度O(n)

代碼:
C++:

/**
 * 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:
    int pathSum(TreeNode* root, int sum) 
    {
        if (!root) return 0;
        queue<TreeNode*> q;
        q.push(root);
        while (!q.empty()) 
        {
            int s = q.size();
            for (int i = 0; i < s; i++) 
            {
                TreeNode* cur = q.front();
                if (cur -> left) q.push(cur -> left);
                if (cur -> right) q.push(cur -> right);
                dfs(cur, sum);
                q.pop();
            }
        }
        return result;
    }
private:
    int result = 0;
    void dfs(TreeNode* root, int sum) 
    {
        if (!root) return;
        sum -= root -> val;
        if (!sum) result++;
        dfs(root -> left, sum);
        dfs(root -> right, sum);
    }
};

Java:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private int result = 0;
    private void dfs(TreeNode root, int sum) {
        if (root == null) return;
        sum -= root.val;
        if (sum == 0) result++;
        dfs(root.left, sum);
        dfs(root.right, sum);
    }
    public int pathSum(TreeNode root, int sum) {
        if (root == null) return 0;
        List<TreeNode> list = new ArrayList<>();
        list.add(root);
        while (!list.isEmpty()) {
            int s = list.size();
            for (int i = 0; i < s; i++) {
                TreeNode cur = list.get(0);
                if (cur.left != null) list.add(cur.left);
                if (cur.right != null) list.add(cur.right);
                dfs(cur, sum);
                list.remove(0);
            }
        }
        return result;
    }
}

Python:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def pathSum(self, root: TreeNode, sum: int) -> int:
        if not root:
            return 0
        return self.check(root, sum) + self.pathSum(root.left, sum) + self.pathSum(root.right, sum)

    def check(self, root: TreeNode, sum: int) -> int:
        if not root:
            return 0
        result = 0
        if sum == root.val:
            result += 1
        result += self.check(root.left, sum - root.val) + self.check(root.right, sum- root.val)
        return result