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

作者 : IT 大叔 本文共1241个字,预计阅读时间需要4分钟 发布时间: 2020-10-13

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

回答:

这可以通过以有序方式遍历树(即离开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);  
免责声明:
1. 本站资源转自互联网,源码资源分享仅供交流学习,下载后切勿用于商业用途,否则开发者追究责任与本站无关!
2. 本站使用「署名 4.0 国际」创作协议,可自由转载、引用,但需署名原版权作者且注明文章出处
3. 未登录无法下载,登录使用金币下载所有资源。
IT小站 » 将二叉树转换为双链表☆☆☆

常见问题FAQ

没有金币/金币不足 怎么办?
本站已开通每日签到送金币,每日签到赠送五枚金币,金币可累积。
所有资源普通会员都能下载吗?
本站所有资源普通会员都可以下载,需要消耗金币下载的白金会员资源,通过每日签到,即可获取免费金币,金币可累积使用。

发表评论