Tìm phép nhân tổng dữ liệu của các lá ở cùng cấp trong Python

Giả sử chúng ta có Cây nhị phân. Chúng tôi phải thực hiện các thao tác sau -

Đối với mỗi cấp độ, hãy tìm tổng của tất cả các lá nếu có các lá ở cấp độ này. Nếu không, hãy bỏ qua nó.
Tìm phép nhân của tất cả các tổng và trả về.

Vì vậy, nếu đầu vào giống như

thì sản lượng sẽ là 270. Hai cấp đầu tiên không có lá. Cấp ba có một lá 9. Cấp cuối cùng có bốn lá 2, 12, 5 và 11. Vậy kết quả là 9 * (2 + 12 + 5 + 11) =270

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

nếu root là null thì
- trả về 0
res:=1
que:=một hàng đợi
chèn thư mục gốc vào cuối hàng đợi
Làm vô hạn -
- no_of_nodes:=kích thước của que
- nếu no_of_nodes giống 0 thì
  - đi ra từ vòng lặp
- sum_level:=0
- found_leaf:=Sai
- trong khi no_of_nodes> 0, thực hiện
  - curr_node:=phần tử đầu tiên của que
  - nếu curr_node là lá thì
    - found_leaf:=True
    - sum_level:=sum_level + curr_node.data
  - xóa phần tử đầu tiên khỏi hàng đợi
  - nếu curr_node.left không phải là null thì
    - chèn curr_node.left vào cuối hàng đợi
  - nếu curr_node.right không phải là null thì
    - chèn curr_node.right vào cuối hàng đợi
  - no_of_nodes:=no_of_nodes - 1
- nếu found_leaf là true thì
  - res:=res * sum_level
trả lại res

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

class TreeNode:
   def __init__(self, data):
      self.data = data
      self.left = self.right = None
def isLeaf(root) :
   return (not root.left and not root.right)
def find_res(root) :
   if (not root) :
      return 0
   res = 1
   que = []
   que.append(root)
   while (True):
      no_of_nodes = len(que)
   if (no_of_nodes == 0) :
      break
   sum_level = 0
   found_leaf = False
   while (no_of_nodes > 0) :
      curr_node = que[0]
      if (isLeaf(curr_node)) :
         found_leaf = True
         sum_level += curr_node.data
         que.pop(0)
         if (curr_node.left != None) :
            que.append(curr_node.left)
         if (curr_node.right != None) :
            que.append(curr_node.right)
         no_of_nodes -=1
      if (found_leaf) :
         res *= sum_level
   return res
root = TreeNode(8)
root.left = TreeNode(8)
root.right = TreeNode(6)
root.left.right = TreeNode(7)
root.left.left = TreeNode(9)
root.left.right.left = TreeNode(2)
root.left.right.right = TreeNode(12)
root.right.right = TreeNode(10)
root.right.right.left = TreeNode(5)
root.right.right.right = TreeNode(11)
print(find_res(root))

Đầu vào

root = TreeNode(8)
root.left = TreeNode(8)
root.right = TreeNode(6)
root.left.right = TreeNode(7)
root.left.left = TreeNode(9)
root.left.right.left = TreeNode(2)
root.left.right.right = TreeNode(12)
root.right.right = TreeNode(10)
root.right.right.left = TreeNode(5)
root.right.right.right = TreeNode(11)

Tìm phép nhân tổng dữ liệu của các lá ở cùng cấp trong Python

Ví dụ

Đầu vào

Đầu ra