30Day LeetCoding Callenge — Week3

這週的難度有點高了，主要是在考資料結構的問題，這週我歸納出兩個技巧

1. Dynamic Programming (動態規劃)
2. 二元搜尋樹

Dynamic Programming

動態規劃的用法，就像是在走訪陣列時就在元素中累計運算，這個很難意會，所以我拿範例來舉例。

30Day LeetCoding Callenge — Week2 ，有用過recursion 做過階乘，但recursion 只能得到結果，而dynamic programming 則是列出1～6階的階乘，這特性的應用在本週有很大的應用，我們拿 1.Product of Array Except Self 做舉例。

題目說可以用O(n)的方式解決，題目的思維在於如何將該元素以外的元素相乘，即可以得出結果。而解題分析可得到如何將元素以外的元素相成，其實就是做出元素左邊跟元素右邊的所有值相乘。

用程式碼來看就是，分別將該元素的左邊跟右邊所有元素乘裡來，只要在兩邊在相乗就可以得到答案，而陣列中可以發現每個值剛好都是左邊或右邊乘起來的積，所以蒐集到特定索引值時，就是該元素得左邊/右邊的乘積。

let L = [1] //因為最右跟最左沒東西所以為1
for(let i = 0 ; i < nums.length-1; i++){
    L[i+1] = (L[i+1-1] * nums[i])
}
let numsR = nums.reverse()
let R = [1] // R為了方便運算所以還需要反轉
for(let i = nums.length ; i  nums.length-1 ; i++){
    R[i+1] = R[i+1-1] * numsR[i]
}
R = R.reverse()

再來有一題也是很精彩的Dynamic Programming 的應用：

3.Minimum Path Sum

這題解法厲害的點在於，使用Dynamic Programming 將第一列跟第一行累加起來變成：

[1,4,5]
[2,5,1]
[6,2,1]

這時候路徑和第一行跟第一列已經有部分處理好了。剩下有可能會走過任一個第一行或第一列的中間的值運算，舉例來說，grid[1][1] 運算時就是加相鄰的最小路徑和也就是grid[0][1] 或grid[1][0]，而這兩個元素又代表的走到這個元素的路徑和，所以繼續累加的話就可以得到終點grid[i][j]的最小路徑和，我認為這題是Week3裡面Dynamic Programming的經典應用。

  for(let i = 1 ; i < row ; i++){
      for(let j = 1 ; j < col ; j++){
          grid[i][j] += Math.min(grid[i-1][j],grid[i][j-1])
      }
  } 

二元搜尋樹

其實這週二元搜尋樹的應用只有一題，但這是經典的資料結構運算，所以還是要了解二元搜尋樹的醍醐味，下面是一顆二元搜尋樹：

二元搜尋樹的特點：

1. 每個節點的左節點會小於節點
2. 每個節點的右節點會大於節點

二元搜尋樹的遍歷，也就是走訪的順序：

1. Preorder Traversal 前序遍歷，中 -> 左 -> 右
2. Inorder Traversal 中序遍歷，左 -> 中 -> 右
3. Postorder Traversal 後序遍歷 左-> 右 ->中

上面簡單介紹，二元搜尋樹的定義及遍歷方式。

題目中我們常看到的二元搜尋樹的陣列為二元堆積，先了解在js中怎麼處理二元堆積。通常leetcode會將需要用的function提供出來，以下是二元樹的Tree Node，其實跟LinkedList的List Node 很像。

 function TreeNode(val) {
    this.val = val;
    this.left = this.right = null;
 }

這週題目剛好就是將陣列轉成二元堆積，所以我們直接看 6.Construct Binary Search Tree from Preorder Traversal ，這題就是將陣列轉成二元搜尋數的前序遍歷的二元堆積。

首先我們先想一下從二元搜尋數的最上層節點開始做，如果要放進Tree Node 的話就要想第一個節點及他的左跟右節點是什麼。

從8開始所以第一個比8小的就是5，5就是8的左子樹，第一個比8大的是10所以10是8的右子樹，所以程式碼就有一個判斷可以參考了：

slice是切掉第一個元素後過濾出後面小於preorder[0]的陣列。
left =  preorder.slice(1).filter(ele => ele < preorder[0])
right = preorder.slice(1).filter(ele => ele > preorder[0])

所以第一個根節點8後就可以切出小於8的左子樹陣列跟大於8的右子樹陣列，之後就是再用遞迴重新指向新的根節點，然後再切出左子樹陣列跟右子樹陣列，直到null。

function TreeNode(val) {
    this.val = val;
    this.left = this.right = null;
}
var bstFromPreorder = function(preorder) {
    if(preorder.length === 0) return null
    if(preorder.length === 1) return new TreeNode(preorder[0])
    let root =  new TreeNode(preorder[0])
    let left  = bstFromPreorder(preorder.slice(1).filter(ele => ele < preorder[0]))
    let right = bstFromPreorder(preorder.slice(1).filter(ele => ele > preorder[0]))
    if(root) root.left = left
    if(root) root.right = right
    return root
};

詳細題解在：https://ithelp.ithome.com.tw/articles/10231122