Sponsored
Sponsored
This approach uses a depth-first search traversal to keep track of the current node's parent and grandparent values. If the grandparent's value is even, the node's value is added to the sum.
We initiate the DFS with the root, setting initial parent and grandparent values as null or zero.
Time Complexity: O(n) where n is the number of nodes. Each node is visited once.
Space Complexity: O(h) where h is the height of the tree due to the recursion stack.
1class TreeNode {
2 int val;
3 TreeNode left;
4 TreeNode right;
5 TreeNode() {}
6 TreeNode(int val) { this.val = val; }
7 TreeNode(int val, TreeNode left, TreeNode right) {
8 this.val = val;
9 this.left = left;
10 this.right = right;
11 }
12}
13
14public class Solution {
15 public int sumEvenGrandparent(TreeNode root) {
16 return dfs(root, null, null);
17 }
18
19 private int dfs(TreeNode node, TreeNode parent, TreeNode grandparent) {
20 if (node == null) return 0;
21 int sum = 0;
22 if (grandparent != null && grandparent.val % 2 == 0) {
23 sum += node.val;
24 }
25 sum += dfs(node.left, node, parent);
26 sum += dfs(node.right, node, parent);
27 return sum;
28 }
29}This Java solution is structured similarly to the Python one. A depth-first search is performed with a recursive function dfs, passing the current node, its parent, and grandparent as parameters. The sum is accumulated whenever a grandparent with an even value is encountered.
Utilizing an iterative method with breadth-first traversal (via a queue) enables level-wise examination of tree nodes. This format offers insight into parent-grandchild relations by leveraging node attributes over iteration.
Time Complexity: O(n), where n is the count of nodes due to single node examination.
Space Complexity: O(w), w being the maximum width of the tree, accounting for queue storage.
#include <queue>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
int sumEvenGrandparent(TreeNode* root) {
queue<pair<TreeNode*, pair<TreeNode*, TreeNode*>>> q;
q.push({root, {nullptr, nullptr}});
int sum = 0;
while (!q.empty()) {
auto [node, parentGrandparent] = q.front();
q.pop();
TreeNode* parent = parentGrandparent.first;
TreeNode* grandparent = parentGrandparent.second;
if (!node) continue;
if (grandparent && grandparent->val % 2 == 0) {
sum += node->val;
}
q.push({node->left, {node, parent}});
q.push({node->right, {node, parent}});
}
return sum;
}
};The C++ implementation follows a similar structure utilizing a queue to systematically pursue level-order traversal. Elements in the queue maintain node, parent, and grandparent associations, enabling easy validation and sum updates.