在Python中将链表转换为之字形二叉树的程序
假设我们有一个单向链表,我们必须使用以下规则将其转换为二叉树路径−
- 链表的头是根。
- 每个后续节点是父节点的左子节点当其值较小时,否则它将是右子节点。
所以,如果输入为[2,1,3,4,0,5],则输出将是
为了解决这个问题,我们将遵循以下步骤−
- 定义一个函数解决()。 这将带来一个节点
- 如果节点为null,则
- 返回null
- root:=创建一个值与节点值相同的树节点
- 如果节点的下一个值不为null,则
- 如果节点的下一个值<节点的值,则
- 根的左侧:= solve(节点的下一个值)
- 否则,
- root的右侧 := solve(下一个节点的值)
- 如果节点的下一个值<节点的值,则
- 返回root
让我们看下面的实现,以获得更好的理解。
示例
class ListNode:
def __init__(self, data, next = None):
self.val = data
self.next = next
def make_list(elements):
head = ListNode(elements[0])
for element in elements[1:]:
ptr = head
while ptr.next:
ptr = ptr.next
ptr.next = ListNode(element)
return head
class TreeNode:
def __init__(self, data, left = None, right = None):
self.data = data
self.left = left
self.right = right
def print_tree(root):
if root is not None: print_tree(root.left)
print(root.data, end = ', ') print_tree(root.right)
class Solution:
def solve(self, node):
if not node:
return None
root = TreeNode(node.val)
if node.next:
if node.next.val < node.val:
root.left = self.solve(node.next)
else:
root.right = self.solve(node.next)
return root
ob = Solution()
L = make_list([2,1,3,4,0,5])
print_tree(ob.solve(L))
输入
[2,1,3,4,0,5]
输出
1, 3, 0, 5, 4, 2,