将一个二叉树转化为双向链表，不开辟新空间

我就是我 2021-12-12 14:29 147阅读 0赞

假设 转后后 节点 的 left 指针 作为 next 指针， right 指针 作为 prev 指针

思路：首先可以利用的指针 即是 叶子节点 的 指针。这样 我们 可以 不断  把 一部分节点 移到 找到的新叶子节点 后面，比如 把 右节点 移到 左叶子几点后面。

简单的想， 假设 我们 把 左右子树已经 转换 好了， 这个时候 我们 我们 只要 把 右子树转换后的链表 添加 到 左子树 的链表 后，将 左子树的 right 指针 指向 根节点。根节点的right指针指向空。

先来 三个 节点

1 空节点 （NULL节点） ：  返回空

2 只有根节点：直接返回

3 有个左孩子： 父节点 left 指针 指向 下一个节点 即 左孩子 ，不变

right 指针 保持 为空 （注意 不是 循环链表，所以 prev 指针 不用指向 尾节点 ）, 即 父节点 保持 不变

左孩子 的 right 指针 指向 父节点 ，left 指针 指向空 不变

4 有个右孩子： 父节点 没有 左孩子，所以 右子树 链表 可以直接 加到 父节点下面 。所以 父节点 的 left 指针 指向 右孩子。right 指针 改为 指向 空

右孩子 没有 下一个节点了，所以 left 指针 为空 不变， 由于前面有父节点，所以 right 指针 指向 父节点

5 左右孩子：先转换 左子树，得到 一个双向链表 ，只有一个节点即左孩子，再转换 右节点 同理。

第二步 将 右子树 的 链表 加到 左子树 的 后面，所以 左孩子的 left 指针 指向 右孩子，右孩子的 right 指针 指向 根节点的左孩子。

第三步 根节点 作为 左孩子的前一个节点 也就是 整个链表的首节点，right 指针指向空，左孩子的 right 指向 根节点。

为了 在 转换 左子树 后 ，将 右子树 加到 左子树形成的链表的后面，转换 函数 返回 链表的 最后一个 节点

python 代码：

class BTree(object):
    
        def __init__(self,v,left=None,right=None):
            self.value = v
            self.left = left
            self.right = right
    
        def toDLink(self):
            def _(node):
                'move right node to left leaf'
                assert node != None
                if node.left == None and node.right == None: # only self, like S2
                    return node
                if node.left == None: # only right , like s4
                    tail = _(node.right) # change right tree
                    node.right.right = node # right child's prev pointer point to father node
                    node.left = node.right # father node's next pointer point to right node
                    node.right = None # father prev pointer point to null
                elif node.right == None: # only left , like s3
                    tail = _(node.left)　# change left tree　　　　　　　　　　　　
                    node.left.right = node # left child prev pointer
                else: # both , like s5
                    ltail = _(node.left)
                    rtail = _(node.right)
                    node.right.right = ltail
                    ltail.left = node.right
                    node.right = None
                    node.left.right = node
                    tail = rtail
                return tail
            _(self)

变形题： 一颗有序二叉树，转换为 一个 有序 双向链表 （2014校招研发笔试）

思路 一样， 只是 不将 右子树 形成 的 链表 加到 左子树形成的链表后 面 罢了。反过来 将 根节点 和 左子树形成的链表 加到 右子树形成的链表后面 ，然后 链表头结点不再一定是根节点，要保存头结点，当然也可以从尾节点回溯过去得到，只是一个正反序的问题。

总的来说 还是 二叉树的 前序，中序 或 后序 遍历。

转载于:https://www.cnblogs.com/i2u9/p/btree2dlink.html