資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法學研究使用 Python 和父指標查詢二叉樹的最低公共祖先的程式
假設我們給定一棵二叉樹以及兩個特定的節點 x 和 y。我們必須從二叉樹中找出這兩個節點的最低公共祖先。二叉樹中的最低公共祖先是指 x 和 y 節點都是其後代的最低節點。特定節點也可以是其自身的後代。我們必須找到該節點並將其作為輸出返回。
樹的節點結構如下所示：
TreeNode: data: <integer> left: <pointer of TreeNode> right: <pointer of TreeNode> parent: <pointer of TreeNode>
在尋找解決方案時，我們必須利用父指標。
因此，如果輸入如下所示：
並且 x = 3，y = 7；則輸出將為 5。
3 和 7 都是 5 的後代，所以答案是 5。
為了解決這個問題，我們將遵循以下步驟：
path_p_r := 一個新的列表
當 x 不為空時，執行：
將 x 插入 path_p_r 的末尾
x := x 的父節點
當 y 不為空時，執行：
如果 path_p_r 中存在 y，則
返回 y
y := y 的父節點
讓我們看看下面的實現以更好地理解：
示例
class TreeNode: def __init__(self, data, left = None, right = None, parent = None): self.data = data self.left = left self.right = right self.parent = parent 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, parent=temp) else: temp.left = TreeNode(0,parent=temp) break else: que.append(temp.left) if (not temp.right): if data is not None: temp.right = TreeNode(data,parent=temp) else: temp.right = TreeNode(0,parent=temp) break else: que.append(temp.right) def make_tree(elements): Tree = TreeNode(elements[0]) for element in elements[1:]: insert(Tree, element) return Tree def search_node(root, element): if (root == None): return None if (root.data == element): return root res1 = search_node(root.left, element) if res1: return res1 res2 = search_node(root.right, element) return res2 def solve(x, y): path_p_r = [] while x: path_p_r.append(x) x = x.parent while y: if y in path_p_r: return y y = y.parent root = make_tree([5, 3, 7, 2, 4, 1, 7, 6, 8, 10]) print(solve(search_node(root, 3), search_node(root, 7)).data)
輸入
[5, 3, 7, 2, 4, 1, 7, 6, 8, 10], 3, 7
輸出
5
更新於：2021年5月29日
138 次瀏覽
廣告