easyTreesPattern: DFS
Sum of Subtree Values Solution
Problem Statement
Given the root of a rooted tree, where each node has an integer value, find the sum of values of all nodes in the subtree rooted at a given target node. The tree is represented using an adjacency list where `adj[i]` contains the children of node `i`. The nodes are 0-indexed.
Examples
Example 1:
Input:{"n":5,"edges":[[0,1],[0,2],[1,3],[1,4]],"values":[10,5,3,2,4],"targetNode":0}
Output:24
Explanation: The subtree rooted at node 0 includes nodes 0, 1, 2, 3, and 4. Their values are 10, 5, 3, 2, and 4. The sum is 10 + 5 + 3 + 2 + 4 = 24.
Example 2:
Input:{"n":5,"edges":[[0,1],[0,2],[1,3],[1,4]],"values":[10,5,3,2,4],"targetNode":1}
Output:11
Explanation: The subtree rooted at node 1 includes nodes 1, 3, and 4. Their values are 5, 2, and 4. The sum is 5 + 2 + 4 = 11.
Example 3:
Input:{"n":3,"edges":[[0,1],[1,2]],"values":[1,2,3],"targetNode":2}
Output:3
Explanation: The subtree rooted at node 2 includes only node 2. Its value is 3. The sum is 3.
Constraints
- 1 <= n <= 10^5, where n is the number of nodes.
- 0 <= node values <= 1000.
- The input represents a valid rooted tree with node 0 as the root.
- 0 <= targetNode < n.
Time: O(N) Space: O(N)
Build an adjacency list to represent the tree. Then, perform a single Depth-First Search (DFS) starting from the `targetNode`. The DFS function will recursively calculate the sum of values for each child's subtree and add it to the current node's value.
Run, Test & Submit Code
Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.
Solve on Interactive WorkspaceTested Solutions
def sum_of_subtree_values(n, edges, values, targetNode):
adj = [[] for _ in range(n)]
for u, v in edges:
adj[u].append(v)
def dfs(node):
current_sum = values[node]
for child in adj[node]:
current_sum += dfs(child)
return current_sum
return dfs(targetNode)