LeetCode - Medium - 1315. Sum of Nodes with Even-Valued Grandparent

我就是我 2022-10-08 11:21 18阅读 0赞

## Topic ##

*  Tree
 *  Depth-first Search

## Description ##

[https://leetcode.com/problems/sum-of-nodes-with-even-valued-grandparent/][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:**

![a29b7b1e3c784bcc37712aecad131044.png][]

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

[https_leetcode.com_problems_sum-of-nodes-with-even-valued-grandparent]: https://leetcode.com/problems/sum-of-nodes-with-even-valued-grandparent/
[a29b7b1e3c784bcc37712aecad131044.png]: /images/20221005/ed78125a3809439da05ab7e3591f4604.png