二叉樹
對于算法題，樹的周遊确實是經常考的（這裡我們隻講二叉樹哈，二叉樹就是指除了葉子節點外，其餘節點都有兩個子節點）。一般就是前序周遊，中序周遊和後序周遊。所謂的前，中，後其實就是指什麼時候周遊根節點。
如圖：這就是一個二叉樹，什麼是前序周遊呢？前序周遊就是先周遊根節點，再周遊左子樹，最後周遊右子樹。我一般實作二叉樹周遊喜歡使用遞歸。以我們這個圖為例，前序：先周遊根節點：A，再周遊左子樹：左子樹是B所在分支，這時候可以把B當做A，進行遞歸。結果是：ABDECFG;
遞歸思路
遞歸其實就是直接或者間接自己調用自己，有一個出口（要是沒有出口會出現死循環）這個出口就是判斷他是不是葉子節點，如果是葉子節點意味着他沒有左右子樹。
代碼實作：
const root = {
val: "A",
left: {
val: "B",
left: {
val: "D"
},
right: {
val: "E"
}
},
right: {
val: "C",
left:{
val:"F",
},
right: {
val: "G"
}
}
};
function preorder(root){
if(!root){
return
}
console.log(root.val)
preorder(root.left)
preorder(root.right)
}
preorder(root)
同理：
如果是中序的話，那我們就先周遊左子樹，再周遊根節點，最後周遊右子樹。
代碼實作：
function preorder(root){
if(!root){
return
}
preorder(root.left)
console.log(root.val)
preorder(root.right)
}
preorder(root)
想必到這：後序周遊大家也知道該怎麼做了吧，這裡就不贅述了。
連結清單
說到連結清單，首先大家得知道連結清單的結構是什麼樣的：
大家可以看到一個節點包含資料域和指針域，資料域就是這個節點儲存的資料，指針域代表下一個結點（後繼結點）的引用。在上篇文章中說數組的時候說過，數組他是順序存儲結構，也就是我們定義了一個大小固定的數組，他是占據一個連續的空間，而連結清單不同，他不是占據連續的空間，類似這樣：
js怎麼寫一個節點呢？簡單
function Node(val){
this.val = val
this.next = null
}
那怎麼實作一個連結清單呢？首先要知道他們之間的聯系是通過指針來實作的。就像上邊我畫的那個圖的紅箭頭就意味着指針。
function Node(val){
this.val = val
this.next = null
}
let a = new Node(1)
let b = new Node(2)
let c = new Node(3)
a.next = b
b.next = c
console.log(a)
log:
連結清單的特點其實就是能夠快速的添加删除元素，有很多人問：為什麼需求是友善添加删除元素我們需要使用連結清單這種資料結構而不是數組呢？其實答案之前我已經給出了，數組他是順序存儲，占據的是一塊連續的存儲空間，而連結清單占據的不連續的，他是靠指針建立的聯系。比如當我們在任意位置增加一個元素，如果是數組的話，這個位置之後的元素是不是得都要往後挪一位，那他的空間複雜度就是O(n),而如果是連結清單的話，我們隻需要将前一個節點的指針指向這個需要添加的元素，把剛添加的這個元素的指針指向前一個元素指針指向的元素即可。
還拿上邊那個例子，我們怎麼在尾部添加一個元素4呢？
function Node(val){
this.val = val
this.next = null
}
let a = new Node(1)
let b = new Node(2)
let c = new Node(3)
let d = new Node(4)
a.next = b
b.next = c
c.next = d
console.log(a)
log:
怎麼往中間添加呢，比如在1和2之間添加一個5
function Node(val){
this.val = val
this.next = null
}
let a = new Node(1)
let b = new Node(2)
let c = new Node(3)
let d = new Node(4)
let e = new Node(5)
a.next = b
b.next = c
c.next = d
//1和2之間添加一個元素5
a.next = e
e.next = b
console.log(a)
log
删除3呢：
連結清單經典例題：翻轉連結清單
function Node(val){
this.val = val
this.next = null
}
let a = new Node(1)
let b = new Node(2)
let c = new Node(3)
a.next = b
b.next = c
let newVal = null
function reverse(head){
while(head){
//把第二個節點存起來
let temp = head.next
//把頭結點的next置空
head.next = newVal
newVal = head
head = temp
}
return newVal
}
const cc = reverse(a)
console.log(cc)
log: