Given the root of a binary tree, return the sum of values of nodes with an even-valued grandparent. If there are no nodes with an even-valued grandparent, return 0.
A grandparent of a node is the parent of its parent if it exists.
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.
Example 2:
Input: root = [1]
Output: 0
Constraints:
The number of nodes in the tree is in the range [1, 104].
1 <= Node.val <= 100
Solutions
Solution 1: DFS
We design a function $dfs(root, x)$, which represents the sum of the values of the nodes that meet the conditions in the subtree with $root$ as the root node and $x$ as the value of the parent node of $root$. The answer is $dfs(root, 1)$.
The execution process of the function $dfs(root, x)$ is as follows:
If $root$ is null, return $0$.
Otherwise, we recursively calculate the answers of the left and right subtrees of $root$, that is, $dfs(root.left, root.val)$ and $dfs(root.right, root.val)$, and add them to the answer. If $x$ is even, we check whether the left and right children of $root$ exist. If they exist, we add their values to the answer.
Finally, return the answer.
The time complexity is $O(n)$, and the space complexity is $O(n)$. Where $n$ is the number of nodes.
1 2 3 4 5 6 7 8 91011121314151617181920
# Definition for a binary tree node.# class TreeNode:# def __init__(self, val=0, left=None, right=None):# self.val = val# self.left = left# self.right = rightclassSolution:defsumEvenGrandparent(self,root:TreeNode)->int:defdfs(root:TreeNode,x:int)->int:ifrootisNone:return0ans=dfs(root.left,root.val)+dfs(root.right,root.val)ifx%2==0:ifroot.left:ans+=root.left.valifroot.right:ans+=root.right.valreturnansreturndfs(root,1)
/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */funcsumEvenGrandparent(root*TreeNode)int{vardfsfunc(*TreeNode,int)intdfs=func(root*TreeNode,xint)int{ifroot==nil{return0}ans:=dfs(root.Left,root.Val)+dfs(root.Right,root.Val)ifx%2==0{ifroot.Left!=nil{ans+=root.Left.Val}ifroot.Right!=nil{ans+=root.Right.Val}}returnans}returndfs(root,1)}