没有完成入门任务的参考安装入门

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

同样还是递归解决，建一个列表用于存储结果，调用递归函数，递归函数需要实现每个节点执行：

1. 任意一个节点，如果值就是key，就返回index
2. 如果值不是key，就查left和right，进行递归，返回array，或者返回None
3. 拿到子叶递归返回的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。后来编写递归，也遇到了很多语法问题，写了很久才完成，收获很大。希望以上思路对你有帮助。