数据结构
网络
关系数据库管理系统 (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 次浏览
广告