Pythonの二分木で2つのノード間の距離を見つけるプログラム

二分木が与えられ、二分木の2つのノード間の距離を見つけるように求められたとします。グラフのように2つのノード間のエッジを見つけ、エッジの数またはそれらの間の距離を返します。ツリーのノードは以下のような構造になっています-

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

したがって、入力が次のような場合

そして、その間の距離を見つけなければならないノードは2と8です。その場合、出力は4になります。

2つのノード2と8の間のエッジは、（2、3）、（3、5）、（5、7）、および（7、8）です。それらの間のパスには4つのエッジがあるため、距離は4です。

これを解決するには、次の手順に従います-

• 関数findLca（）を定義します。これはルート、p、q
  を取ります
  • rootがnullと同じ場合、
    • nullを返す
  • ルートのデータが（p、q）のいずれかである場合、
    • ルートを返す
  • left：=findLca（rootの左側、p、q）
  • right：=findLca（rootの権利、p、q）
  • 左右がnullでない場合は、
    • ルートを返す
  • 左または右に戻る
• 関数findDist（）を定義します。これはルートになります、data
  • queue：=新しい両端キュー
  • キューの最後に新しいペア（ルート、0）を挿入します
  • キューが空でないときに、実行します
    • current：=キューの左端のペアの最初の値
    • dist：=キューの左端のペアの2番目の値
    • 現在のデータがデータと同じである場合、
      • return dist
    • 現在の左側がnullでない場合、
      • ペア（現在の左側、dist + 1）をキューに追加します
    • 現在の権利がnullでない場合、
      • ペア（current.right、dist + 1）をキューに追加します
• node：=findLca（root、p、q）
• return 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