将二叉树转换为双链表☆☆☆

主题：二叉树除法与征服链接列表递归数据结构

回答：

这可以通过以有序方式遍历树（即离开child -> root ->right节点）来实现。

在有序遍历中，首先遍历左侧的子树，然后访问根，最后遍历右侧的子树。

解决此问题的一种简单方法是从一个空的双向链表开始。在执行二叉树的有序遍历时，请始终将每个元素输出插入到双向链表中。但是，如果我们仔细地看问题，访问者希望我们将二叉树就地转换为双向链表，即我们不应该为双向链表创建新节点。

可以使用分而治之的方法递归解决此问题。下面是指定的算法。

从根节点开始，递归求解左右子树
在每个步骤中，处理完左右子树后：
- 将左子树的输出与根融合，以得到中间结果
- 将中间结果（在上一步中构建）与右侧子树的输出融合在一起，以生成当前递归调用的最终结果

复杂度分析：

时间复杂度：O（n）
空间复杂度：O（n）

递归解决方案具有内存复杂性，因为它将消耗堆栈上的内存，直到二叉树的高度。它适用于平衡树，最坏的情况下可以。O(h)hO(log n)O(n)

实现方式：

爪哇

public static void BinaryTreeToDLL(Node root) {
    if (root == null)
        return;
    BinaryTreeToDLL(root.left);
    if (prev == null) { // first node in list
        head = root;
    } else {
        prev.right = root;
        root.left = prev;
    }
    prev = root;
    BinaryTreeToDLL(root.right);
    if (prev.right == null) { // last node in list
        head.left = prev;
        prev.right = head;
    }
}

Y

def BinaryTreeToDLL(self, node):    
    #Checks whether node is None    
    if(node == None):    
        return;    

    #Convert left subtree to doubly linked list    
    self.BinaryTreeToDLL(node.left);    

    #If list is empty, add node as head of the list    
    if(self.head == None):    
        #Both head and tail will point to node    
        self.head = self.tail = node;    
    #Otherwise, add node to the end of the list    
    else:    
        #node will be added after tail such that tail's right will point to node    
        self.tail.right = node;    
        #node's left will point to tail    
        node.left = self.tail;    
        #node will become new tail    
        self.tail = node;    

    #Convert right subtree to doubly linked list    
    self.BinaryTreeToDLL(node.right);

常见问题FAQ