Sum of Nodes with Even-Valued Grandparent

Description

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 10^4.
• The value of nodes is between 1 and 100.

Solution(javascript)

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
// /**
//  * @param {TreeNode} root
//  * @return {number}
//  */
// const sumEvenGrandparent = function (root) {
//   let result = 0
//   const sum = (node) => {
//     let current = [node]
//     let level = 0
//     while (level < 2 && current.length > 0) {
//       const next = []
//       level += 1
//       current.forEach((nextNode) => {
//         if (nextNode.left) {
//           next.push(nextNode.left)
//         }
//         if (nextNode.right) {
//           next.push(nextNode.right)
//         }
//       })
//       current = next
//     }
//     return level === 2
//       ? current.reduce((acc, currentNode) => acc + currentNode.val, 0) : 0
//   }
//   const aux = (node) => {
//     if (!node) {
//       return
//     }
//     aux(node.left)
//     if (node.val % 2 === 0) {
//       result += sum(node)
//     }
//     aux(node.right)
//   }
//   aux(root)
//   return result
// }

/** 记录 parent 和 grandParent, O(N)
 * @param {TreeNode} root
 * @return {number}
 */
const sumEvenGrandparent = function (root) {
  let result = 0
  const aux = (node, parent, grandParent) => {
    if (!node) {
      return
    }
    if (grandParent && grandParent.val % 2 === 0) {
      result += node.val
    }
    aux(node.left, node, parent)
    aux(node.right, node, parent)
  }
  aux(root)
  return result
}