真诚请问大家怎么搞懂并迅速写出recursion 卡住了。。。

转专业小白刚接触数据结构 由于智商捉急 在树那里痛苦不已
比如一个操作 把一个类似于线性的degenerate tree 转成一个完全balance tree（test时候的node数目保证可以建complete balance tree）
想到的办法是每次找中点 作为新的root
断开新root右边 连上原来的root
然后对左边重复操作
对右边重复操作
最后自然就平衡了
但是写的时候用recursion自己把自己绕死了 怎么也想不通程序怎么样通过recursion一步一步实现

请问大家有什么经验传授么
当年各位大神们都是怎么掌握recursion写法的 。。。

ps此题如果用rotate怎么做呢？就是不断开任何原树的left or right链接情况下
可能单纯通过rotate做到成为完全平衡树么

多看，多走点例子。
有困难的话也可以看看youtube上大家的视频。
给自己内心留够时间去品味。

补充内容 (2018-8-3 18:59):
推荐题目: max depth of binary tree

树是特殊的图， 都是图的特殊用法。更应该看general一点的图， 然后再看具体的树。

你如果什么都不懂还是先读点书吧，简单的算法数据结构你大概明白怎么回事再来看具体的题

补充内容 (2018-8-4 09:35):
recursion是一种思路， 想法， divide & conquer。
像mergesort， quicksort都用到了， 这些你看明白的吧？

至于你说旋转， 那不是说不能做，但是非常麻烦。

你root右边的数字，应该变成root右边的最左边数...

抛砖引玉一下：
1. 定义函数的precondition和postcondition
2. 假设每次递归调用后postcondition满足（induction hypothesis），证明每次递归调用前precondition满足
3. 证明函数最后返回时postcondition满足

然后呢， 弄明白了吗？发个贴就算完事了？

尝试一下画解空间树，从简单的case开始，然后总结出条件

肥宅快乐水 发表于 2018-8-5 23:40
然后呢， 弄明白了吗？发个贴就算完事了？

后来。。。就。。。。自己研究明白了啊。。。

肥宅快乐水 发表于 2018-8-4 09:33
树是特殊的图， 都是图的特殊用法。更应该看general一点的图， 然后再看具体的树。

你如果什么都不懂还 ...

你root右边的数字，应该变成root右边的最左边数...
哦 我就是这么做的 但是在我们老师的看法里这不是旋转 这是叫splice 因为你断开了当前新root和他prev的链接
所以至于怎样理解他所谓的旋转 并不懂