30Day LeetCoding Callenge — Week3
這週的難度有點高了，主要是在考資料結構的問題，這週我歸納出兩個技巧
- Dynamic Programming (動態規劃)
- 二元搜尋樹
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])
}
}
二元搜尋樹
其實這週二元搜尋樹的應用只有一題，但這是經典的資料結構運算，所以還是要了解二元搜尋樹的醍醐味，下面是一顆二元搜尋樹：
二元搜尋樹的特點：
- 每個節點的左節點會小於節點
- 每個節點的右節點會大於節點
二元搜尋樹的遍歷，也就是走訪的順序：
- Preorder Traversal 前序遍歷，中 -> 左 -> 右
- Inorder Traversal 中序遍歷，左 -> 中 -> 右
- 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
};