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 and 100.

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)));
    }
}