โปรแกรมหาความยาวของพาธต่อเนื่องที่ยาวที่สุดของไบนารีทรีใน python

สมมติว่าเรามีต้นไม้ไบนารี เราต้องหาเส้นทางที่ยาวที่สุดในไบนารีทรี

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

จากนั้นผลลัพธ์จะเป็น 5 ตามลำดับที่ยาวที่สุดต่อเนื่องกันคือ [2, 3, 4, 5, 6]

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

• ถ้ารูทเป็นโมฆะ
  • คืน 0
• maxPath :=0
• กำหนดฟังก์ชัน helper() นี่จะใช้โหนด
• inc :=1, ธันวาคม :=1
• ถ้าทางซ้ายของโหนดไม่เป็นโมฆะ
  • [left_inc, left_dec] :=helper(left of node)
• มิฉะนั้น
  • [left_inc, left_dec] :=[0, 0]
• ถ้าทางขวาของโหนดไม่เป็นโมฆะ
  • [right_inc, right_dec] :=helper(ทางขวาของโหนด)
• มิฉะนั้น
  • [right_inc, right_dec] :=[0, 0]
• ถ้าด้านซ้ายของโหนดไม่เป็นโมฆะและค่าของโหนด - ค่าของโหนดด้านซ้ายเท่ากับ 1 ดังนั้น
  • inc :=สูงสุดของ inc และ (left_inc + 1)
• มิฉะนั้นเมื่อด้านซ้ายของโหนดไม่เป็นโมฆะและค่าของโหนด - ค่าของโหนดด้านซ้ายจะเหมือนกับ -1 ดังนั้น
  • ธ.ค :=สูงสุดของ ธ.ค. และ (left_dec + 1)
• หากสิทธิ์ของโหนดไม่เป็นโมฆะและค่าของโหนด - ค่าของสิทธิ์ของโหนดเท่ากับ 1 ดังนั้น
  • inc :=สูงสุดของ inc และ (right_inc + 1)
• มิฉะนั้นเมื่อสิทธิ์ของโหนดไม่เป็นโมฆะและค่าของโหนด - ค่าของโหนดทางขวาเท่ากับ -1 ดังนั้น
  • ธ.ค :=สูงสุดของ ธ.ค. และ (right_dec + 1)
• ถ้าด้านซ้ายของโหนดไม่เป็นโมฆะ และด้านขวาของโหนดไม่เป็นโมฆะ และค่าของโหนดด้านซ้าย - ค่าของโหนดเหมือนกับ 1 และค่าของโหนด - ค่าของโหนดด้านขวาเท่ากับ 1 ดังนั้น
  • maxPath :=สูงสุดของ maxPath และ (left_dec + right_inc + 1)
• มิฉะนั้น เมื่อโหนดด้านซ้ายไม่เป็นโมฆะ และด้านขวาของโหนดไม่เป็นโมฆะ และค่าของโหนดด้านซ้าย - ค่าของโหนดเหมือนกับ -1 ดังนั้น
  • maxPath :=สูงสุดของ maxPath และ (left_inc + right_dec + 1)
• maxPath :=สูงสุดของ maxPath, inc และ dec
• return inc, ธ.ค.
• จากวิธีหลัก ให้ทำดังนี้:
• ตัวช่วย(ราก)
• ส่งคืน maxPath

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

ตัวอย่าง

คลาส TreeNode:def __init__(ตัวเอง ข้อมูล ซ้าย =ไม่มี ขวา =ไม่มี):self.val =ข้อมูล self.left =ซ้าย self.right =ขวา def print_tree(root):ถ้า root ไม่ใช่ None:print_tree (root.left) พิมพ์ (root.val, end =', ') คลาส print_tree (root.right) วิธีแก้ไข:def แก้ (ตัวเอง, รูท):ถ้าไม่ใช่ root:ส่งคืน 0 self.maxPath =0 def helper (โหนด) :inc, dec =1, 1 ถ้า node.left:left_inc, left_dec =helper(node.left) อื่น:left_inc, left_dec =0, 0 ถ้า node.right:right_inc, right_dec =helper (node.right) อื่น:right_inc , right_dec =0, 0 ถ้า node.left และ node.val - node.left.val ==1:inc =max(inc, left_inc + 1) elif node.left และ node.val - node.left.val ==-1:dec =max(dec, left_dec + 1) ถ้า node.right และ node.val - node.right.val ==1:inc =max(inc, right_inc + 1) elif node.right และไม่ใช่ de.val - node.right.val ==-1:dec =max(dec, right_dec + 1) if (node.left และ node.right และ node.left.val - node.val ==1 และ node.val - node.right.val ==1):self.maxPath =สูงสุด (self.maxPath, left_dec + right_inc + 1) elif (node.left และ node.right และ node.left.val - node.val ==-1 และ node.val - node.right.val ==-1):self.maxPath =max(self.maxPath, left_inc + right_dec + 1) self.maxPath =max(self.maxPath, inc, dec) ส่งคืน inc, ธ.ค. helper(root) ส่งคืน self.maxPath ob =Solution()root =TreeNode(3)root.left =TreeNode(2)root.right =TreeNode(4)root.right.left =TreeNode(5)root.right.right =TreeNode(9)root.right.left.left =TreeNode(6)พิมพ์(ob.solve(root))

อินพุต

ผลลัพธ์

5