在 Python 中找出二叉树中两个节点之间的距离的程序

• Z时代
• 2024-01-10
• 分类：综合

假设给定一棵二叉树，并要求我们找出二叉树中两个节点之间的距离。我们像在图中一样找出两个节点之间的边，并返回边的数量或它们之间的距离。树的节点具有以下结构 -

data : <integer value>
right : <pointer to another node of the tree>
left : <pointer to another node of the tree>

所以，如果输入像

并且我们必须找到之间距离的节点是2和8；那么输出将是4。

两个节点 2 和 8 之间的边是：(2, 3)、(3, 5)、(5, 7) 和 (7, 8)。它们之间的路径中有 4 条边，因此距离为 4。

示例

让我们看看以下实现以更好地理解 -

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
   ifroot.datain (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()
      ifcurrent.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

以上是 在 Python 中找出二叉树中两个节点之间的距离的程序 的全部内容， 来源链接： utcz.com/z/363249.html