二分木の引数xのノードの深さを返す関数

Question

以下のような二分木のルートについて

class Node:
    def __init__(self,value):
        self.value =value
        self.left =None
        self.right =None
    def __str__(self):
        return str(self.value)
top =Node(1)
node_l =Node(2)
node_r =Node(3)
top.left =node_l
top.right =node_r
node_l_l=Node(4)
node_l_r=Node(5)
node_l.left =node_l_l
node_l.right =node_l_r
node_r_l =Node(6)
node_r.left =node_r_l
node_l_r_l =Node(7)
node_l_r.left =node_l_r_l
node=top.left
print(node)

ノードtopと、値xを引数にとりノードの深さを返す関数について考えています。

例えば

depth(top,7)ならば
3
depth(top,1)ならば
0
depth(top,8)ならば
-1

と返し、値xがノードに含まれていなければ(例えば8など)-1と返すような関数です。

お力添えいただければ幸いです。

Answer 1

こんな感じかと〜

def depth(node, x, level=0):
  if node.value == x:
    return level
  for child in [node.left, node.right]:  
    if child:
      lv = depth(child, x, level+1)
      if lv >= 0:
        return lv
  return -1

???? replitで動作確認してみた

Comments

[Angela_Nakasugi]

うまく動作しました。ありがとうございます。