Leetcode 437. Path Sum III

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.

简单的归递。

public class Solution { public int pathSum(TreeNode root, int sum) { if (root == null) return 0; int res = 0; res += dfs(root, sum); res += pathSum(root.left, sum); res += pathSum(root.right, sum); return res; } private int dfs(TreeNode node, int remain) { int tmp = 0; if (node.left != null) tmp += dfs(node.left, remain-node.val); if (node.right != null) tmp += dfs(node.right, remain-node.val); if (remain == node.val) tmp++; return tmp; } }