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

  }

}

1091, Shortest path in binary matrix

1091, Shortest path in binary matrix

====

BFS,

Shortest path,

Path existed

====

1. 題目給予vec<vec<int>>matrix

從左上 欲走到右下

路徑上只能是0 可以走八個方向

2. 一個queue< pair<int,int>>做BFS

一個vec<vec<bool>> visited記錄走過

3. 起點是左上

找它的鄰近加入queue

紀錄每次queue.size

而後每次找鄰近 且 matrix[][]==0 加入queue

4. 每次round++

當有座標碰到右下

return round(左上）

====

class Solution {

public:

int shortestPathBinaryMatrix(.vec<vec<int>>& grid ){

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

  if( grid[0][0]!=0 || grid[m-1][n-1]!=0 ) return -1

  queue< pair<int,int>> pq

  pq.push({1,0}), pq.push({0,1}), pq.push({1,1})

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

  int res=1 //第一輪

  while(!pq.empty()){

    int qSize= pq.size()

    for(int t-qSize){

      auto qFront= pq.front()

      pq.pop()

      int x= qFront.first

      int y= qFront.second

      

      if(x==m-1 && y==n-1) return res+1 //第n輪加上右下+1

      if(x>=0 && y>=0 && x<m && y<n && !visited[x][y] && grid[x][y]==0){

        visited[x][y]=true

        pq.push({x-1,y-1}), pq.push({x-1,y}), pq.push({x-1,y+1})

        pq.push({x,y-1}), pq.push({x,y+1})

        pq.push({x+1,y-1}), pq.push({x+1,y}), pq.push({x+1,y+1})

      }//if

    }//for qSize

    res++

  }//while q.empty

  return -1

}

};

994, rotting oranges

====

994, rotting oranges

====

BFS,

Shortest path,

Path existed

====

1. 給予一個箱子

'0'代表空

'1'代表好的

'2'代表爛的橘子

每分鐘爛的會向四個方向腐爛

求最大（久）箱子內還有好的

2. 起點是爛的->爛的(2) 座標/pair加入queue

隨後加入找好的(1)

但是要把它變爛(2)才 座標/pair加入queue

3. 多一個int fresh紀錄剩餘的好的

每次BFS加入記得扣掉

多一個int res紀錄第幾輪

return res

//剛開始的BFS還沒開始感染

//所以放在while裡面即可

4. 四個方向化成一個vector

vec<int> for={-1, 0, 1, 0, -1}

//只要1234, 2345 pair就好

====

class Solution{

public:

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

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

  int fresh=0

  queue< pair<int,int>> q

  for i-m

    for j-n

      if grid[i][j] == 2

        q.push(<i-1,j>), q.push(<i+1,j>), q.push(<i,j-1>), q.push(<i,j+1>);

      if grid[i][j] == 1

        fresh++

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

  int res=-1

  while( !q.empty() ){

    int qSize= q.size()

    while(qSize--){

      auto fq= q.front()

      q.pop()

      int x= fq.first

      int y= fq.second

      if(x>=0 && y>=0 && x<m && y<n && !visited[x][y] && grid[x][y]==1){

        visited[x][y]=true

        grid[x][y]=2

        q.push(<x-1,y>), q.push(<x+1,y>), q.push(<x,y-1>), q.push(<x,y+1>);

      }//if

    }//q.size

    res++

  }//q.empty

if(res==-1) return 0

if(fresh>0) return -1 //有橘子永遠不爛 莫急

}

};

1162, As far from land as possible

====

1162, As far from land as possible

====

BFS,

Shortest path

Path existed

====

1. 目標是water, '0'

能有與

起點land, '1'能有的最長距離

2. 

定義一個queue<pair<int,int>>存放座標

BFS第一輪找的是起點->從'1'開始上下左右加第一輪BFS

3. 當queue不為空

front && pop座標

如果符合條件 //!visited && 是目標'0'

=>

visited true/ update cost/ 加入上下左右BFS

4. 當最遠的座標找到 會結束

=>

最遠的座標 在上一輪會將上下左右加入queue

=>

新的一輪 for step++

=>

都不符合條件 pop

一直都沒有符合條件的座標 所以都沒有加入queue

=>

while queue空了 跳出

=>

這次的step無作用

step-1才是預期

====

class Solution{

public:

int maxDistance( vec<vec<int>>& matrix ){

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

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

  queue<pair<int,int>> pq

  for i-m

    for j-n

      if matrix(i,j) == 1

        pq.push(i-1,j)

        pq.push(i+1,j)

        pq.push(i,j-1)

        pq.push(i,j+1)

  int step=0

  while(!pq.empty()){

    step++

    int size=pq.size()

    for t-size{

    int x= pq.front().first

    int y= pq.front().second

    pq.pop()

    if( x>=0 && y>=0 && x<m && y<n && matrix(x,y)==0 && !visited(x,y) ){

      visited(x,y) = true

      pq.push(x-1,y)

      pq.push(x+1,y)

      pq.push(x,y-1)

      pq.push(x,y+1)

    }//if

    }//for

  }//while

  return step==1? -1: step-1

}

};

542, 01_matrix

====

542, 01_matrix

====

BFS,

Shortest path

Path existed

====

1. 題目希望將給予的matrix

化成

每個單元離它最近的'0'的距離

2. BFS用的是queue, 因為用了座標

所以用queue< pair<int,int> >來紀錄加入queue的座標

3. 從(0,0)開始做BFS

當queue不為空的時候

-> pop單元

-> 針對pop的動作處理BFS //加入新的單元

//新增step or cost

4. Visited是必須的

產生一個vec<vec<bool>>visited來紀錄已經處理過的單元

以免單元間產生無窮迴圈

->

當沒有visited

且

符合題目條件

則處理

BFS //push

====

class Solution{

public:

vec<vec<int>> updateMatrix( vec<vec<int>>&matrix ){

  int m= matrix.size()

  int n= matrix[0].size()

  queue<pair<int,int>> pq

  for i-m

    for j-n

      if(matrix(i,j) == 0){

      //先從'0'開始 因為第一次與零的距離是“0”

      //之後逐漸加一

        pq.push({i-1, j});

        pq.push({i+1, j});

        pq.push({i, j-1});

        pq.push({i,j-1});

        //上下左右加入queue //所有第一層的node

      }

  int step=0

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

  while( !pq.empty() ){

  step++

  int size= pq.size() //紀錄當前的queue size來控制當次需要做多少次

  for(i=0; i<size; i++){

    auto Front= pq.front()

    int x=Front.first

    int y=Front.second

    pq.pop()

    if(x>=0&& y>=0&& x<m&& y<n&& !visited(x,y)&& matrix(x,y)==1){

      //開始找‘1’,因為開始要填1到0的距離

      visited(x,y)=true

      matrix(x,y)=step

      //因為拜訪過了 且當前的距離已經填入

      pq.push({x-1, j});

      pq.push({x+1, j});

      pq.push({i, y-1});

      pq.push({i,y-1});

      //第n次層的上下左右 加入queue

    }//if

  }//for

  }//while

}

};