AlphaCamp Leetcode 訓練營 07. Recursion

課程資訊

此為Alphacamp的Leetcode訓練營課程，內文僅為個人心得。

Recursion(遞迴)

一個function(函式)不停調用function本身。一個基本function是輸入argument後輸出value，而遞迴函式會執行General Case不停呼叫自己，直到滿足Base case才會停止。

例子-費式數列

• Time: BigO (2^n)
• Space:BigO(n)
• 可以用樹狀節點方式表示各function(runtime)執行步驟
• 遞迴的最大「深度」為空間複雜度

參考

• Data Structure — Recursion Basics

練習題：

24. Swap Nodes in Pairs

link

解法：

解法1

解法2

解法3

練習題：

78. Subsets

link

解法：

1. 給一個陣列result，內有一個空陣列為基礎[[]]
2. nums每個el跟給的陣列內的陣列元素做比較，如果該el大於陣列內的最後一個元素，則放入該陣列，回傳目前的組合給下個函式迭代

EX: 目前tempArr陣列是[[1],[2],[3]],nums是[1,2,3]
[1]可以放2,3
[2]可以放3
[3]因為沒有任何元素大於3，所以什麼都不放

EX: 目前tempArr陣列是[[1,2],[1,3],[2,3]],nums是[1,2,3]
[1,2]可以放3
[1,3]因為最後一個元素是3，nums沒有任何元素大於3，所以什麼都不放
[2,3]因為最後一個元素是3，nums沒有任何元素大於3，所以什麼都不放

DFS

javascript - LeetCode Discuss

Backtracking

回溯法用於尋找問題所有可能解，運用遞迴建立所有解，並在過程中移除不可能的組合，最後得到正確解。

236. Lowest Common Ancestor of a Binary Tree

link

解法：

124. Binary Tree Maximum Path Sum

link

解法：