938, range sum of BST

938, range sum of BST

====

tree, BST

DFS

BFS

====

DFS:

1. 如何開始: 先從root開始

每次都加

node(如果符合range則node->value 否則0), 

node->left, 

node->right

2. 如何結束: 如果本身!node 就return 0

====

class Solution {

public:

  int rangeSumBST(TreeNode* root, int L, int H){

    if(!root) return 0

    return (root->val >= L && root->val <=H ? root->val : 0) + rangeSumBST(root->left, L, H) + rangeSumBST(root->right, L, H)

  }

}

====

BFS:

1. 如何開始: root加到queue, 每次加左子右子

2. 如何停止: queue空

====

class Solution {

public:

  int rangeSumBST(TreeNode* root, int L, int H){

    queue<TreeNode*> pq

    int sum=0

    pq.push(root)

    while(!pq.empty()){

      TreeNode* cur = pq.front

      pq.pop()

      if(cur->val >= L && cur->val <= H)

        sum+=cur->val

      if(cur->left) pq.push(cur->left)

      if(cur->right) pq.push(cur->right)

    }//while pq.empty

  return sum

  }

}

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

  }

}

1302, Deepest leaves sum

====

1302, Deepest leaves sum

====

tree

DFS, BFS

====

DFS:

1. 題目給一個TreeNode

從(root, 0//lvl, depth)開始DFS

2. 懶人法, vec<int>sum[i] 紀錄每i層depth的total

在DFS中

如果sum size等於傳入的lvl, 則表示這層depth第一次加入到sum, 所以sum.push_back

否則, 表示已經有index 'lvl', 加入到sum[lvl]

//初始root 0, sum size也零, sum.push_back == sum[0]

//root右子樹 1, sum size卻是2, 表示有左子樹加入過了, 合併到sum[lvl] == sum[1]

3. 最終return vector最後一個元素 == sum.back

----

class Solution {

public:

  vec<int> sum

  int deepestLeaveSum(TreeNode* root){

    dfs(root, 0)

    return sum.back()

  }

  void dfs(TreeNode* node, int lvl){

    if(sum.size() == lvl)

      sum.push_back(node->val)

    else

      sum[lvl] += node->val

    if(node->left) dfs(node->left, lvl+1)

    if(node->right) dfs(node->right, lvl+1)

  }

}

====

BFS:

1. 題目給一個TreeNode

依照lvl/depth加入queue, pop all並加總

2. 懶人法, 當queue不等於空

把sum清空

並且元素pop all並加總//for, 這樣就會得到每一層的sum

如果還有左子右子, push到queue

如果queue空, 表示最後一層leave做完了, return當次/最終sum

----

class Solution {

public:

  int sum

  int deepestLeaveSum(TreeNode* root) {

    queue<TreeNode*> q

    q.push(root)

    while(!q.empty()){

      sum=0

      int qlen = q.size()

      for(int i=0, i<qlen, i++) {

        TreeNode* node = q.front()

        q.pop()

        sum+=node->val

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

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

      }//for qlen

    }//while q.empty

    return sum

  }

}

802, Find eventual safe states

====

802, Find eventual safe states

====

DFS,

cycle find

有向/無向圖找cycle不一樣

有向需要三個顏色(還沒看過/ 還在看/ 已經看完

無向需要兩個顏色(visited/ un-visited

過程中有碰到訪問過/看過的node

就是有cycle

====

a)

1. 題目給予一個graph

定義一個int dp(n, 0)初值

0, 還沒看過

-1,還在看

1,已經看完

2. DFS一進去

先將dp[i]=-1 //還在看

然後針對graph[i][]一一DFS檢查

如果有false則return false

3. 如果graph[i][]跑完 都沒看到cycle 

//如果沒有看到dp==-1, i.e還在看

則dp[i]=1, i.e已經看完

return true

else

return dp[i]==1

4. main一個for跑DFS

如果false,就不加入結果

否則是安全的,加入

====

class Solution{

public:

bool DFS( vec<vec<int>>&graph, vec<int>&dp, int i){

  if ( dp[i] ) //-1 ->false, 1 ->true

    return dp[i]==1

  dp[i]=-1

  for auto t:graph[i].begin; t!=graph[i].end; t++

    if ( !DFS( graph, dp, *t ) )

      return false

  dp[i]=1

  return true;

}

vec<int> eventualSafe( vec<vec<int>>&graph ){

  int n=graph.size()

  vec<int> res

  vec<int> dp(n, 0)

  for i-n

    if( DFS( graph, dp, i )

      res.push_back(i)

  return res

}

}

733, Flood Fill

====

733, Flood Fill

====

DFS,

from each un-visited node/island problems

====

1. 題目給予一個vec<vec<int>>M

一個起始的座標

以及變更的新數值

2. 定義一個vec<vec<bool>>visited

DFS( M, visited, i, j, m, n, new )走過上下左右的同值/同於起始 的所有node

====

class Solution{

void DFS( vec<vec<int>>& matrix, vec<vec<bool>>&visited, int i, int j, int m, int n, int old, int new){

  if( i<0 || j<0 || i>=m || j>=n || matrix(i,j)!=old || visited(i,j) ) return;

  visited(i,j)= true;

  matrix(i,j)= new;

  DFS( matrix, visited, i-1, j, m, n, matrix(i,j), new)

  DFS i+1

  DFS j-1

  DFS j+1

}

vec<vec<int>> FloodFill( vec<vec<int>>& matrix, int x, int y, int newColor ){

  int m= matirx.size(), n= matrix[0].size()

  vec<vec<bool>> visited= (m, false)

  if matrix(x,y)!=newColor

    DFS( matrix, visited, x, y, matrix(x,y), newColor)

  return matrix

}

841, Keys and rooms

====

841, Keys and rooms

====

DFS,

for each unvisited node/island problems

====

1. 題目給予固定長度n的房間 以及房間內含的鑰匙

題目定義第一間是沒有鎖的=>DFS開始的地方

生成一個n的visited

2. DFS走過所有的鑰匙

最終for檢查visited

如果還有房間un-visited則false

====

class Solution{

public:

void DFS( vec<vec<int>>&rooms, vec<bool>&visited, int node){

  visited[node]=true

  for auto k:rooms[node]

    if( !visited[k] )

      DFS( rooms, visited, k )

}

bool VisitedRoom( vec<vec<int>>& rooms ){

  int n=rooms.size()

  vec<bool> visited(n, false)

  DFS( rooms, visited, 0 )

  int i=0

  for i-n

    if !visited[i] return false

  return true

}  

1254, Number of closed islands

====

1254, Number of closed islands

====

DFS from each unvisited node/island problem

====

a)

----

1. 題目給予一個vec<vec<char>>的網絡（grid

生成一個vec<vec<bool>>的visited

來表示這個node是不是檢查過了

//因為DFS有上下左右 可能先前被查過了

2. （看題目）定義DFS的行為:

DFS( grid, visited, i, j, m, n )

->

如果超界, 如果是'0', 如果造訪過了 return

else, 

visited改成true

這個node的上下左右去做DFS

3. 回到main（看題目）定義main的行為:

for for grid

如果是'1', 如果還沒造訪過 則

DFS( grid, visited, i, j, m, n )

count++

//因為DFS會做完, 能連到的都連完了, 才跳出

//就找到一個island

//如果for又找到 應該又是全新的island 故重新算重新加

====

class Solution{

void DFS( vec<vec<int>>&grid, vec<vec<bool>>&visited, int i, j, m, n){

  if i<0 || j<0 || i>=m || j>=n || visited(i,j) || grid(i,j)!='1'

    return

  visited(i,j)=true

  DFS( grid, visited, i-1, j, m, n)

  DFS(i+1

  DFS(j-1

  DFS(j+1

}

public:

int closedIsland (vec<vec<int>>&grid){

  int m=grid.size()

  int n=grid[0].size()

  vec<vec<bool>> visited(m, vec<bool>(n, false))

  int count=0

  for i-m

    for j-n

      if( grid [i][j] == '1' && !visited[i][j] ){

        DFS( grid, visited, i, j, m, n)

        count++

      }

  return count

}

};

1376, Time needed to inform all employees

====

1376, Time needed to inform all employees

====

DFS,

Time taken to reach all nodes, or share info to all graph nodes

====

1. 題目給予一個vec<int> manager

=>

生成一份vec<vec<int>> children

or

map<int, vec<int>> children

children用意在紀錄node擁有的child

(可視為hash map

2. 因為children會紀錄所mana<->child關係

所以從root(題目給的headID) 開始DFS

會走過所有node

3. 題目給予一個 vec<int>informTime

定義一個resource 為最終total結果

每次DFS,

一個current為加上目前informTime[i]的時間

每次DFS 比較max(resource, current)

最終return resource

====

class Solution{

int DFS( vec<vec<int>>&child, int node, vec<int>&time){

if child[node].size == 0

  return 0

  //本次node沒有children, time沒有增加, return

int ans= time[node]

int tempMax= 0

for(auto c: child[node]){

  tempMax = max( tempMax, DFS( child, c, informTime)

//如果child有多個 會停在for裡面

//當有找到更大的結果 會丟給tempMax

//當次還沒return就不會被清零

//清零用意只是紀錄當次node子集裡的最大

}

return ans+tempMax

//結果等於 當前的time[node] 

//加上

//子集裡面最大的time

}

public:

int numOfMinute( int n, int headID, vec<int>& manager, vec<int>& informTime){

vec<vec<int>> children(n)

for int i=0; i<n; i++

  if manager[i] != -1

    children[ manager[i] ].push_back(i)

return DFS( children, headID, informTime )

}

130, Surrounded regions

130, Surrounded regions

====

DFS boundary

====

1. 題目是說被1包圍的0 可以被翻牌

=>

沒有碰到邊界的0 可以被翻牌

（有連結到）碰到邊界的0無法被翻牌

2. 從邊界開始找有沒有0

當找到邊界為0, 對它的做DFS(上下左右)

找到的0, 先把它變更符號e.g.#

3. for, for go through

剩下的0是可以翻成1的

剩下的#是不能翻的 翻回0

====

class Solution{

public:

  void surroundRegion(vec<vec<char>>&board){

    int m=board.size(), n=board[0].size()

    for int i=0; i<m; i++

      if board[i][0] == 'o'

        DFS(board, i, 0, m, n)

      if board[i][n-1] == 'o'

        DFS(board, i, n-1, m, n)

    for int j=0; j<n; j++

      if board[0][j] == 'o'

        DFS(board, 0, j, m, n)

      if board[m-1] == 'o'

        DFS(board, m-1, j, m, n)

    for i-n

      for j-n

        if board[i][j] == 'o'

          board[i][j] = 'x'

        if board[i][j] == '#'

          board[i][j] = 'o'

}

void DFS(vec<vec<char>>board, int i, j, m, n){

  if i<0 || j<0 || i>=m || j>=n || board(i,j)!='o'

    return

  board(i,j) = '#'

  DFS(i-1, j, m, n)

  DFS(i+1, j, m, n)

  DFS(i, j-1, m, n)

  DFS(I, j+1, m, n

}