没有完成入门任务的参考安装入门
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。后来编写递归，也遇到了很多语法问题，写了很久才完成，收获很大。希望以上思路对你有帮助。