โปรแกรมหาจำนวนสูงสุดของโหนดที่ไม่อยู่ติดกันของต้นไม้ใน Python

สมมติว่าเรามีไบนารีทรี เราต้องหาผลรวมสูงสุดของค่าที่หาได้เนื่องจากไม่มีค่าสองค่าใดที่จะสามารถอยู่ติดกับพาเรนต์กับชายด์ได้

ดังนั้นหากอินพุตเป็นแบบ

แล้วผลลัพธ์จะเป็น 17 เป็น 10, 4, 3 ไม่อยู่ติดกัน

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

กำหนดฟังก์ชัน f() นี่จะใช้โหนด
ถ้าโหนดเป็น null แล้ว
- ส่งคืน (0, 0)
(a, b) :=f(ซ้ายของโหนด)
(c, d) :=f(ทางขวาของโหนด)
คืนค่าคู่ (ค่าสูงสุดของโหนด + b + d และ a + c, a + c)
จากการเรียกเมธอดหลัก f(root) และคืนค่าแรกของมัน

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

class TreeNode:
def __init__(self, data, left = None, right = None):
   self.val = data
   self.left = left
   self.right = right
def f(node):
   if not node:
      return 0, 0
   a, b = f(node.left)
   c, d = f(node.right)
   return max(node.val + b + d, a + c), a + c
class Solution:
   def solve(self, root):
      return f(root)[0]
ob = Solution()
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(10) root.left.left = TreeNode(4) root.left.right = TreeNode(3) print(ob.solve(root))

อินพุต

root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(10)
root.left.left = TreeNode(4)
root.left.right = TreeNode(3)