题目给定一个二叉树要求原地將它展开为链表。
在python 二叉树中树的实现一般为:
也就是说,在本题中我们要通过某种方式将树中所有节点的左子树都接到右子树的位置,然后令左子树为None最后,所有的节点都会表现为左子树为None右子树相连的情况,以此代替链表中的self.next
下面我们来结合代码,分析一下這是怎么实现的
有很多刚接触递归的朋友都可能不太了解,下面这两句是什么意思
接下来的代码也不难理解就是前面说的将左树移到右边,然後右树接到后面的过程
有小伙伴可能又要问了,为什么不直接像以下这样操作呢
这不是刚好原来的右树接到原来左树后吗?我一开始寫的时候也犯了这个错误让我们来结合图示看一下。
第一次递归回去好像是对的。
但第二次递归回去就明显不对了这是因为我们将原来的右树直接接在原来的左树上,丢失了3和4节点因此,我们要在这里加一个while循环确保接到最后面的节点,即本题的节点4这样才正確。