在Python中查找二叉树中两个节点之间距离的程序
假设我们有一棵二叉树并被要求查找二叉树中两个节点之间的距离。我们像在图中一样找到两个节点之间的边,并返回边数或它们之间的距离。树的一个节点具有以下结构 −
data: <整数值>
right: <指向树的另一个节点的指针>
left : <指向树的另一个节点的指针>
因此,如果输入是
我们需要查找的两个节点为2和8,那么输出为4。
两个节点2和8之间的边为:(2,3),(3,5),(5,7)和(7,8)。它们之间的路径上有4个边,因此距离为4。
要解决这个问题,我们将遵循以下步骤−
- 定义findLca()函数。这将使用root,p和q
- 如果root与null相同,则
- 返回null
- 如果root的数据是(p,q)中的任何一个,则
- 返回root
- left := findLca(root的左子树,p,q)
- right := findLca(root的右子树,p,q)
- 如果left和right不为null,则
- 返回root
- 返回left或right
- 如果root与null相同,则
- 定义findDist()函数。这将使用root和数据
- queue :=一个新的deque
- 在队列末尾插入一个新的二元组(root, 0)
- 当队列不为空时,执行以下操作:
- current :=队列中左侧二元组的第一个值
- dist:队列中左侧二元组的第二个值
- 如果current的数据与输入数据相同,则
- 返回dist
- 如果current的左子节点不为null,则
- 将二元组(当前节点的左子节点,dist+1)添加到队列中
- 如果current的右子节点不为null,则
- 将二元组(current.right,dist+1)添加到队列中
- node := findLca(root,p,q)
- 返回findDist(node,p) + findDist(node,q)
示例
让我们看看以下实现以更好地理解−
import collections
class TreeNode:
def __init__(self, data, left = None, right = None):
self.data = data
self.left = left
self.right = right
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):
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 print_tree(root):
if root is not None:
print_tree(root.left)
print(root.data, end == ', ')
print_tree(root.right)
def findLca(root, p, q):
if root is None:
return None
if root.data in (p,q):
return root
left = findLca(root.left, p, q)
right = findLca(root.right, p, q)
if left and right:
return root
return left or right
def findDist(root, data):
queue = collections.deque()
queue.append((root, 0))
while queue:
current, dist = queue.popleft()
if current.data == data:
return dist
if current.left: queue.append((current.left, dist+1))
if current.right: queue.append((current.right, dist+1))
def solve(root, p, q):
node = findLca(root, p, q)
return findDist(node, p) + findDist(node, q)
root = make_tree([5, 3, 7, 2, 4, 6, 8])
print(solve(root, 2, 8))
输入
root = make_tree([5, 3, 7, 2, 4, 6, 8])
print(solve(root, 2, 8))
输出
4