用 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(left of root, p, q)
  • right := findLca(right of root, p, q)
  • 如果 left 和 right 不为 null，则
    • 返回 root
  • 返回左或右
• 定义一个函数 findDist() 。这将获取 root，数据
  • queue := 一个新的双端队列
  • 在队列末尾插入一个新的对 (root, 0)
  • 当队列不为空时，执行
    • current := 队列中最左边对的第一个值
    • dist := 队列中最左边对的第二个值
    • 如果 current 的数据与数据相同，则
      • 返回 dist
    • 如果 current 的 left 不为空，则
      • 将对 (current 的 left, dist+1) 添加到队列
    • 如果 current 的 right 不为空，则
      • 将对 (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

相关文章

• Python 中通过 K 扩展列表
• Python - 使用交替的 0 和 1 初始化列表
• Python 中元组列表到字典的转换
• Python - 从两个列表中配对，使得成对的元素不相同
• 使用 Python 和 SQLite 的 SQL
• 使用 pytrie 模块在 Python 中进行前缀匹配
• 创建和访问 Python 包
• 如何使用正则表达式和数据类型选择多个 DataFrame 列
• 如何在 Pandas 中查找和过滤重复行?
• 用 Python 编写程序以正确的顺序查找机场?

有用资源

• python 参考教程 - 该教程包含有关 python 的更多信息:https://www.cainiaomax.com/python/