Given a binary tree, return the sum of values of nodes with even-valued grandparent. (A grandparent of a node is the parent of its parent, if it exists.)
If there are no nodes with an even-valued grandparent, return 0
.
Example 1:
Input: root = [6,7,8,2,7,1,3,9,null,1,4,null,null,null,5] Output: 18 Explanation: The red nodes are the nodes with even-value grandparent while the blue nodes are the even-value grandparents.
Constraints:
- The number of nodes in the tree is between
1
and10^4
. - The value of nodes is between
1
and100
.
Solution: Recursion
Time complexity: O(n)
Space complexity: O(n)
C++
1 2 3 4 5 6 7 8 9 10 |
// Author: Huahua class Solution { public: int sumEvenGrandparent(TreeNode* root, int p = 1, int gp = 1) { if (!root) return 0; return sumEvenGrandparent(root->left, root->val, p) + sumEvenGrandparent(root->right, root->val, p) + (gp & 1 ? 0 : root->val); } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment