欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

1315. Sum of Nodes with Even-Valued Grandparent

程序员文章站 2022-03-23 17:58:38
...

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:
1315. Sum of Nodes with Even-Valued Grandparent
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 10^4.
The value of nodes is between 1 and 100.

hint1:Traverse the tree keeping the parent and the grandparent.
hint2:If the grandparent of the current node is even-valued, add the value of this node to the answer.

  public int sumEvenGrandparent(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);
    }
 class Solution {
	    public int sumEvenGrandparent(TreeNode root) {
	    return helper(root,null,null); //Perform DFS
	    }    
	  private int helper(TreeNode current,TreeNode parent,TreeNode grandParent){
	    int sum=0;
	    if(current==null) return 0;
	    if(grandParent!=null && grandParent.val % 2 == 0){
	         sum+=current.val;
	    }
	    sum+= helper(current.left,current,parent);
	    sum+=helper(current.right,current,parent);
	    return sum;
	}
}
public int sumEvenGrandparent(TreeNode root) {
        int sum = 0;
        Queue<TreeNode> q = new LinkedList();
        q.add(root);
        
        //LevelOrderTraversal
        while(!q.isEmpty()) {
            TreeNode node = q.poll();
            if(node.left != null) {
                q.add(node.left);
                if(node.val % 2 == 0) {
                    if(node.left.left != null) {
                        sum += node.left.left.val;
                    }
                    if(node.left.right != null) {
                        sum += node.left.right.val;
                    }
                }
            }

            if(node.right != null) {
                q.add(node.right);
                if(node.val % 2 == 0) {
                    if(node.right.left != null) {
                        sum += node.right.left.val;
                    }
                    if(node.right.right != null) {
                        sum += node.right.right.val;
                    }
                }
            }
        }
        
        return sum;
    }
相关标签: leetcode中等