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.
1#include <iostream>
2using namespace std;
3
4struct TreeNode {
5 int val;
6 TreeNode *left;
7 TreeNode *right;
8 TreeNode(int x) : val(x), left(NULL), right(NULL) {}
9};
10
11class Solution {
12public:
13 int sumEvenGrandparent(TreeNode* root) {
14 return dfs(root, nullptr, nullptr);
15 }
16
17private:
18 int dfs(TreeNode* node, TreeNode* parent, TreeNode* grandparent) {
19 if (!node) return 0;
20 int sum = 0;
21 if (grandparent && grandparent->val % 2 == 0) {
22 sum += node->val;
23 }
24 sum += dfs(node->left, node, parent);
25 sum += dfs(node->right, node, parent);
26 return sum;
27 }
28};In C++, we define a structurally similar solution using a depth-first search. Nodes are explored recursively, and sums are accumulated if their grandparent (when non-null) has an even value.
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.
The Java solution makes use of a queue structure to store node trios (node, parent, grandparent) for effective level-wise traversal. Each node checked is appended with appropriate ancestors in the queue, summing valid ones.