LeetCode 1315: Sum of Nodes with Even-Valued Grandparent Solution
Master LeetCode problem 1315 (Sum of Nodes with Even-Valued Grandparent), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.
1315. Sum of Nodes with Even-Valued Grandparent
Problem Explanation
Explanation
To solve this problem, we can perform a depth-first traversal of the binary tree while keeping track of the parent and grandparent values for each node. If a node has an even-valued grandparent, we add its value to the total sum. We can achieve this by passing the parent and grandparent values recursively in our traversal.
- Start with the root node and initialize the sum to 0.
- Recursively traverse the tree, passing the current node, its parent value, and its grandparent value to the function.
- If the grandparent value is even, add the current node's value to the sum.
- Continue the traversal for the left and right children of the current node.
- Return the total sum at the end.
Time complexity: O(N) where N is the number of nodes in the tree. Space complexity: O(H) where H is the height of the tree.
Solution Code
class Solution {
public int sumEvenGrandparent(TreeNode root) {
return dfs(root, 1, 1);
}
private int dfs(TreeNode node, int parent, int grandparent) {
if (node == null) {
return 0;
}
int sum = 0;
if (grandparent % 2 == 0) {
sum += node.val;
}
sum += dfs(node.left, node.val, parent);
sum += dfs(node.right, node.val, parent);
return sum;
}
}Try It Yourself
Loading code editor...
Related LeetCode Problems
Frequently Asked Questions
How to solve LeetCode 1315 (Sum of Nodes with Even-Valued Grandparent)?
This page provides optimized solutions for LeetCode problem 1315 (Sum of Nodes with Even-Valued Grandparent) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.
What is the time complexity of LeetCode 1315 (Sum of Nodes with Even-Valued Grandparent)?
The time complexity for LeetCode 1315 (Sum of Nodes with Even-Valued Grandparent) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.
Can I run code for LeetCode 1315 on DevExCode?
Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1315 in Java, C++, or Python.