沒有完成入門任務的參考安裝入門
Puzzling Pyramids 是 Cairo 的 數據結構與算法任務 Think Cairo 的第二篇，主要解決二叉樹問題，共有兩個小題。
中序 DFS#
如圖需要把二叉樹從左到右轉換為列表，稍微懂算法就知道是中序的 DFS (深度優先搜索)，可以在互聯網上搜到很多解析。
在實際寫 cairo 代碼時，當遇到該如何定義空 array，如何索引等問題，可以參考 https://book.cairo-lang.org/ch03-01-arrays.html
lower_chambers 是 Option 類型，不知道如何操作 Option 類型可參考 https://book.cairo-lang.org/ch06-02-the-match-control-flow-construct.html?highlight=Option#matching-with-options
這個問題可用非遞歸的方式解決，也可用遞歸方式來解決。由於 cairo 的 array 內置函數不夠（寫上一個任務應該能感受到），實際寫起來會更麻煩。所以建議用遞歸來寫。
可先看看官方的 fib 的遞歸版本，道理是一樣的 https://github.com/starkware-libs/cairo/blob/main/examples/fib_array.cairo
遞歸函數實現每個節點執行 "判斷並遞歸左葉 -> 添加節點 -> 判斷並遞歸右葉" 的邏輯。
有幾個重點：
- 遞歸需要把元素 append 到列表裡，該列表需要加上 ref 關鍵字，在遞歸中會引用同一個 array。
- 遞歸函數也需要實現 Clone和 Drop，寫法和 PyramidIntoArray 中一樣。但 GitHub 庫裡的 cairo 新版本寫法有點不同。
- chambers 先轉成 snapshot，就可以多次引用不會導致所有權問題。再用 clone 轉回原來的類型，append 進列表裡。
- 如果測試不通過，可用
use debug::PrintTrait;和[變量].print();去 debug
搜索路徑#
第二小題需要實現搜索路徑，同樣是 DFS，但比第一題要難寫得多。
測試用例如下，尋找 k，需要返回 [h,l,j,k]
h
d l
b f j n
a c e g i k m o
同樣還是遞歸解決，建一個列表用於存儲結果，調用遞歸函數，遞歸函數需要實現每個節點執行：
- 任意一個節點，如果值就是 key，就返回 index
- 如果值不是 key，就查 left 和 right，進行遞歸，返回 array，或者返回 None
- 拿到子葉遞歸返回的 array，append 上當前 index
例如上面測試用例的 j 進行遞歸，得到 Option::None 和 [k].append(j)，返回到 l 節點就是 [k,j].append(l) 和 Option::None，返回到 h 就是 [k,j,l].append(h)。（以上都需要換成 index 操作，原因見下面的注意事項）
由於 cairo 不支持 append_front，只能往後面 append，最後寫個 loop 翻轉得到的路徑 array
注意事項：
- 如果出現 out of gas，建議在遞歸中只操作 index，在最後的 loop 裡用 index 去拿實際的 item
- loop 時，array 需要 .span () 後才能用 pop_back 移除最後的值。具體查看 https://github.com/starkware-libs/cairo/blob/main/corelib/src/array.cairo
總結#
如果算法基礎不好，任務還是挺難的。一開始我用的非遞歸方法，最終遇到了 ref array 的循環賦值語言層面報錯 bug。後來編寫遞歸，也遇到了很多語法問題，寫了很久才完成，收穫很大。希望以上思路對你有幫助。