樹：建立、追踪、找樹葉、算距離

 class Node:

  def __init__(self,key):

    self.left = None

    self.right = None

    self.val = key

  

def find_leaf_nodes(root):

  if root is None:

    return

  if root.left is None and root.right is None:

    print(root.val,end=' ')

  find_leaf_nodes(root.left)

  find_leaf_nodes(root.right)

  

def find_leaf_distances(root,distance):

  global total_distance

  if root is None:

    return

  if root.left is None and root.right is None:

    print(f'leaf {root.val} to root distance：{distance}')

    total_distance+=distance

  find_leaf_distances(root.left,distance+1)

  find_leaf_distances(root.right,distance+1)

  

def pre_order(root):

  if root:

    print(root.val,end=' ')

    pre_order(root.left)

    pre_order(root.right)

def in_order(root):

  if root:

    pre_order(root.left)

    print(root.val,end=' ')

    pre_order(root.right)

def post_order(root):

  if root:

    pre_order(root.left)

    pre_order(root.right)

    print(root.val,end=' ')

root = Node(50)

root.left = Node(30)

root.right = Node(70)

root.left.left = Node(20)

root.left.left.left = Node(15)

root.left.left.right = Node(25)

root.left.right = Node(40)

root.right.left = Node(60)

root.right.right = Node(80)

total_distance = 0

print('pre_order')

pre_order(root)

print('in_order')

in_order(root)

print('post_order')

post_order(root)

print('leaf')

find_leaf_nodes(root)

print('distance')

find_leaf_distances(root,0)

print('total distance：',total_distance)

# Output:

# pre_order

# 50 30 20 15 25 40 70 60 80 in_order

# 30 20 15 25 40 50 70 60 80 post_order

# 30 20 15 25 40 70 60 80 50 leaf

# 15 25 40 60 80 distance

# leaf 15 to root distance：3

# leaf 25 to root distance：3

# leaf 40 to root distance：2

# leaf 60 to root distance：2

# leaf 80 to root distance：2

# total distance： 12