将二叉树转换为双链表☆☆☆
回答:
这可以通过以有序方式遍历树(即离开child -> root ->right
节点)来实现。
在有序遍历中,首先遍历左侧的子树,然后访问根,最后遍历右侧的子树。
解决此问题的一种简单方法是从一个空的双向链表开始。在执行二叉树的有序遍历时,请始终将每个元素输出插入到双向链表中。但是,如果我们仔细地看问题,访问者希望我们将二叉树就地转换为双向链表,即我们不应该为双向链表创建新节点。
可以使用分而治之的方法递归解决此问题。下面是指定的算法。
- 从根节点开始,递归求解左右子树
- 在每个步骤中,处理完左右子树后:
- 将左子树的输出与根融合,以得到中间结果
- 将中间结果(在上一步中构建)与右侧子树的输出融合在一起,以生成当前递归调用的最终结果
复杂度分析:
时间复杂度:O(n)
空间复杂度:O(n)
递归解决方案具有内存复杂性,因为它将消耗堆栈上的内存,直到二叉树的高度。它适用于平衡树,最坏的情况下可以。O(h)
h
O(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小站 » 将二叉树转换为双链表☆☆☆
1. 本站资源转自互联网,源码资源分享仅供交流学习,下载后切勿用于商业用途,否则开发者追究责任与本站无关!
2. 本站使用「署名 4.0 国际」创作协议,可自由转载、引用,但需署名原版权作者且注明文章出处
3. 未登录无法下载,登录使用金币下载所有资源。
IT小站 » 将二叉树转换为双链表☆☆☆
常见问题FAQ
- 没有金币/金币不足 怎么办?
- 本站已开通每日签到送金币,每日签到赠送五枚金币,金币可累积。
- 所有资源普通会员都能下载吗?
- 本站所有资源普通会员都可以下载,需要消耗金币下载的白金会员资源,通过每日签到,即可获取免费金币,金币可累积使用。