1315, Sum of nodes with even-vlaues grandparent

====

1315, Sum of nodes with even-vlaues grandparent

====

tree,

DFS,

BFS

====

DFS:

1. 照順序 從root檢查 root's parent/grandparent

加總sum(global

左子/右子樹加入dfs

2. 如何起始：root, Null, Null

如何停止：檢查左子右子是否空 才扔DFS

----

class Solution {

public:

  int sum=0

  int sumEvenGradparent(TreeNode* root){

    dfs(root, null, null)

    return sum

  }

  void dfs(TreeNode* node, TreeNode* parent, TreeNode* grandpa){

    if(!root) return

    if(grandpa && grandpa->val%2==0)

      sum += root->val

    if(node->left) dfs(node->left, node, parent)

    if(node->right) dfs(node->right, node, parent)

  }

}

====

BFS:

1. 如何起始：q.push(root)

如何停止：

for整個程式->while q.empty時停止

for加總->如果node為空就return 0, 不然就return node->val

2. q.push左子 右子

應該在while !q.empty內

但是在node->val%2外

因為目的是走過/檢查過所有的node, 因此不侷限在%2的case

----

class Solution{

public:

  int sum=0

  int func(TreeNode* root){

    return root? root->val : 0

  }

  int sumEvenGrandparent(TreeNode* root){

    if(!root) return

    queue<TreeNode*> q

    q.push(root)

    while(!q.empty()){

      TreeNode* node = q.front()

      q.pop()

      if(node->val%2==0){

        if(node->left){

          sum+= func(node->left->left) + func(node->left->right)

        }

        if(node->right){

          sum+= func(node->right->left) + func(node->right->right)

        }

      }//if even

      if(node->left) q.push(node->left)

      if(node->right) q.push(node->right)

    }//while q.empty

    return sum

  }

}