資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究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 時，執行以下操作：
- 將 start 的值新增到 arr 的末尾
- 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
更新於: 2021年10月19日
157 次檢視
廣告