30Day LeetCoding Callenge — Week2

這禮拜多了幾題Linked List，Linked List 在js是用nested object 取代的，

如果要做Linked List 的運算則還要考慮到遞迴的用法。

這禮拜的重點技巧：

1. Linked List （鏈結串列)
2. Recursion （遞迴）

LinkedList

LinkedList在javascript的呈現為：

{
  val:0,
  next:{
    val:1,
    next:null
  }
}

如果JS要做鏈結串列的話就必須自己建立function製造

要先有Node節點，每個節點會要的資料，如果有需要可以多塞value進去

class Node{
    constructor(data, next = null){
        this.data = data,
        this.next = next
    }
}

建立LinkedList 的開頭

class LinkedList{
    constructor(){
        this.head = null;
    }
}

在設計塞入節點的function，執行後會發現最後一個是陣列最開始的值，這是正常的，因為程式是把現有的 this.head 塞進 nweNode.next 合併在蓋回原本的this.head。

詳細可再參考：Linked Lists in JavaScript (ES6 code)

LinkedList.prototype.insertAtBeginning = function(data){
    let newNode = new Node(data);
    newNode.next = this.head; 
    this.head = newNode;
    return this.head;
}

題目

1. Middle of the Linked List

說明：找出Linked List 的中間節點,抓出中間節點以後的Linked List

思維：找出Linked List 中間的節點然後回傳節點往後的LinkedList。這題目是應用如何從LinkedList 取得資料，這邊就會先暫存當下的節點，然後取的資料後再把next的資料蓋到暫存得值，直到拿到符合的答案。

var middleNode = function(head) {
    let listLength = 1 
    let a = 0
    let test = head
    
    while(test.next){
        test = test.next
        listLength += 1
    }
    
    let mid = Math.floor(listLength / 2) + 1
    let answer = head
    
    while(mid > 0 && head){
        answer = head
        head = head.next
        mid--
    }
    
    return answer
};

Recusion

recusion 是一個不好懂的演算法，但也是一個常見的基本技巧，我們先用階乘(factorail) 6! Demo!

看起來就是在function內重複呼叫自己，但要注意需要下判斷是終止回調(callback)

所以在 num - 1 = 1 的時候就回傳 1 這樣最會在 2 * 1 的時候結束。

題目

以下有幾題是有相關應用的題目，詳細解題思路可以參考

4.Diameter of Binary Tree

說明：算出二元樹的兩端節點最遠距離

Example:

Given a binary tree
          1
         / \
        2   3
       / \     
      4   5
ans :3 

思維：這題依照資料結構的答案思路，就是計算左邊的最深度及右邊的最深度，所以會用Recusion 跑到node == null 也就是節點的終點結束，因為不知道多長不能假設迴圈的index所以用Recusion是最適合的。

Answer：

let max 
var diameterOfBinaryTree = function(root) {
    max = 1
    dfs(root)
    return max -1
};
const dfs = node =>{
    if(node === null) return 0
    let left = dfs(node.left)
    let right = dfs(node.right)
    max = Math.max(max,left + right + 1)
    return Math.max(left,right)  + 1
}