Chương trình tìm tổng từng phần tử đường chéo trong cây nhị phân bằng Python

Giả sử chúng ta có một cây nhị phân, chúng ta phải tìm tổng của mỗi đường chéo trong cây bắt đầu từ trên xuống dưới bên phải.

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

thì đầu ra sẽ là [27, 18, 3] như các đường chéo là [12,15], [8,10], [3]. Vì vậy, các giá trị tổng là [27, 18, 3]

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

Định nghĩa một hàm traverse (). Thao tác này sẽ lấy nút, numLeft, đầu ra

• nếu nút là null, thì

  • trở lại

• if numLeft> =size of output, then

  • chèn dữ liệu của nút vào cuối đầu ra

• nếu không,

  • output [numLeft]:=output [numLeft] + dữ liệu của nút

• nếu bên trái của nút không rỗng, thì

  • đi ngang (bên trái của nút, numLeft + 1, đầu ra)

• nếu bên phải của nút không rỗng, thì

  • đi ngang (bên phải của nút, numLeft, đầu ra)

• Từ phương thức chính, thực hiện như sau -

• output:=một danh sách mới

• đi ngang (gốc, 0, đầu ra)

• trả lại kết quả đầu ra

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

Ví dụ

class TreeNode:
   def __init__(self, data, left = None, right = None):
      self.data = data
      self.left = left
      self.right = right
class Solution:
   def solve(self, root):
      output = []
      def traverse(node, numLeft, output):
         if not node:
            return
         if numLeft >= len(output):
            output.append(node.data)
         else:
            output[numLeft] += node.data
         if node.left:
            traverse(node.left, numLeft+1, output)
         if node.right:
            traverse(node.right, numLeft, output)
      traverse(root, 0, output)
      return output
ob = Solution()
root = TreeNode(12)
root.left = TreeNode(8)
root.right = TreeNode(15)
root.left.left = TreeNode(3)
root.left.right = TreeNode(10)
print(ob.solve(root))

Đầu vào

root = TreeNode(12)
root.left = TreeNode(8)
root.right = TreeNode(15)
root.left.left = TreeNode(3)
root.left.right = TreeNode(10)

Đầu ra

[27, 18, 3]