Chương trình kiểm tra xem mỗi giá trị nút ngoại trừ các lá có phải là tổng giá trị con của nó hay không trong Python

Giả sử chúng ta có một cây nhị phân, chúng ta phải kiểm tra xem đối với mọi nút trong cây ngoại trừ các lá, giá trị của nó có giống với tổng giá trị con bên trái và giá trị con bên phải của nó hay không.

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

thì đầu ra sẽ là True

Để 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 dfs (). Điều này sẽ bắt nguồn từ gốc

• nếu root là null thì

  • trả về True

• nếu bên trái của thư mục gốc là null và bên phải của thư mục gốc là null, thì

  • trả về True

• trái:=0

• nếu bên trái của thư mục gốc không phải là null, thì

  • left:=giá trị của left of root

• phải:=0

• nếu quyền root không rỗng thì

  • right:=giá trị của quyền gốc

• trả về true khi (trái + phải giống với giá trị của root) và dfs (trái của root) là true và dfs (phải của root) là true

• Từ phương thức chính, hãy làm như sau -

• trả về dfs ​​(gốc)

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.val = data
      self.left = left
      self.right = right
class Solution:
   def solve(self, root):
      def dfs(root):
         if root == None:
            return True
         if root.left == None and root.right == None:
            return True
         left = 0
         if root.left:
            left = root.left.val
         right = 0
         if root.right:
            right = root.right.val
         return (left + right == root.val) and dfs(root.left) and
      dfs(root.right)
return dfs(root)
ob = Solution()
root = TreeNode(18)
root.left = TreeNode(8)
root.right = TreeNode(10)
root.left.left = TreeNode(3)
root.left.right = TreeNode(5)
print(ob.solve(root))

Đầu vào

root = TreeNode(18) root.left = TreeNode(8) root.right = TreeNode(10)
root.left.left = TreeNode(3) root.left.right = TreeNode(5)

Đầu ra

True