在Python中查找给定二叉树中是否存在链接列表的程序
假设给定一个具有根节点“root”的二叉树和具有头节点“head”的链接列表。 我们必须找出该链接列表是否存在于该二叉树中。 如果树中一组节点彼此之间按照链接列表的顺序具有链接,并且如果该顺序与提供的链接列表相似,则返回“True”,否则返回“False”。
因此,如果输入如下所示
树
链接列表
则输出将为True。
为了解决此问题,我们将遵循以下步骤:
- arr :=一个新列表
- size := arr的大小
- temp_arr :=一个大小为(size + 1)的数组,初始化为-1
- 定义一个helper()函数。 这将采用root,val
- 如果val>size,则
- 返回True
- 如果root与None相似,则
- 返回False
- val:= val + 1
- 当val>0且root的值与arr[val-1]的值不同时,执行
- val:=temp_arr[val-1]+1
- 如果helper(root的左节点,val)或helper(root的右节点,val)为True,则
- 返回True
- 返回False
- 如果val>size,则
- start:=head
- 当start不同于null时,执行
- 在arr的末尾添加start的值
- start:=start的下一个
- 对于从1到size + 1的范围内的节点,执行
- temp_arr[node]:=temp_arr[node – 1] + 1
- 当temp_arr[node]>0且arr[node – 1]的值与arr[temp_arr[node] – 1]的值不同时,执行
- temp_arr[node]:=temp_arr[temp_arr[node] – 1] + 1
- 返回helper(root,0)
示例
让我们看看以下实现,以获得更好的理解——
class TreeNode:
def __init__(self, val, left=None, right=None):
self.val = val
self.left = left
self.right = right
class ListNode:
def __init__(self, val, next=None):
self.val = val
self.next = next
def insert(temp,data):
que = []
que.append(temp)
while (len(que)):
temp = que[0]
que.pop(0)
if (not temp.left):
if data is not None:
temp.left = TreeNode(data)
else:
temp.left = TreeNode(0)
break
else:
que.append(temp.left)
if (not temp.right):
if data is not None:
temp.right = TreeNode(data)
else:
temp.right = TreeNode(0)
break
else:
que.append(temp.right)
def make_tree(elements):
node = TreeNode(elements[0])
for element in elements[1:]:
insert(node, element)
return node
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
def solve(root, head):
arr = []
start = head
while start:
arr += (start.val,)
start = start.next
size = len(arr)
temp_arr = [-1] * (size + 1)
for node in range(1, size + 1):
temp_arr[node] = temp_arr[node - 1] + 1
while temp_arr[node] > 0 and arr[node - 1] != arr[temp_arr[node] - 1]:
temp_arr[node] = temp_arr[temp_arr[node] - 1] + 1
def helper(root, val):
if val >= size:
return True
if not root:
return False
val += 1
while val > 0 and root.val != arr[val - 1]:
val = temp_arr[val - 1] + 1
if helper(root.left, val) or helper(root.right, val):
return True
return False
return helper(root, 0)
root = make_tree([6, 7, 8, 9, 10])
head = make_list([6, 7, 10])
print(solve(root, head))
输入
root = make_tree([6, 7, 8, 9, 10])
head = make_list([6, 7, 10])
print(solve(root, head))
输出
True