Topic
- Tree
- Depth-first Search
Description
https://leetcode.com/problems/sum-of-nodes-with-even-valued-grandparent/
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
and 1 0 4 10^4 104. - The value of nodes is between
1
and100
.
Analysis
方法一:自己写的,DFS。
方法二:别人写的,DFS,更精简。
Submission
import com.lun.util.BinaryTree.TreeNode;
public class SumOfNodesWithEvenValuedGrandparent {
//方法一:自己写的,DFS
public int sumEvenGrandparent(TreeNode root) {
if(root == null) return 0;
int result = 0;
if((root.val & 1) == 0) {
TreeNode left = root.left;
if(left != null) {
if(left.left != null)
result += left.left.val;
if(left.right != null)
result += left.right.val;
}
TreeNode right = root.right;
if(right != null) {
if(right.left != null)
result += right.left.val;
if(right.right != null)
result += right.right.val;
}
}
return result + sumEvenGrandparent(root.left) + sumEvenGrandparent(root.right);
}
//方法二:别人写的,DFS
public int sumEvenGrandparent2(TreeNode root) {
return helper(root, 1, 1);
}
public int helper(TreeNode node, int p, int gp) {
if (node == null) return 0;
return helper(node.left, node.val, p) + helper(node.right, node.val, p) + (gp % 2 == 0 ? node.val : 0);
}
}
Test
import static org.junit.Assert.*;
import org.junit.Test;
import com.lun.util.BinaryTree;
public class SumOfNodesWithEvenValuedGrandparentTest {
@Test
public void test() {
SumOfNodesWithEvenValuedGrandparent sObj = new SumOfNodesWithEvenValuedGrandparent();
assertEquals(18, sObj.sumEvenGrandparent( //
BinaryTree.integers2BinaryTree(6,7,8,2,7,1,3,9,null,1,4,null,null,null,5)));
assertEquals(18, sObj.sumEvenGrandparent2( //
BinaryTree.integers2BinaryTree(6,7,8,2,7,1,3,9,null,1,4,null,null,null,5)));
}
}