สมมติว่าเรามีไบนารีทรีที่ไม่ว่างเปล่าหนึ่งต้น เราต้องหาผลรวมของเส้นทาง ดังนั้นที่นี่ เส้นทางคือลำดับของโหนดใดๆ จากโหนดเริ่มต้นบางโหนดไปยังโหนดใดๆ ในที่ที่มีการเชื่อมต่อพาเรนต์-ชายด์ พาธต้องมีอย่างน้อยหนึ่งโหนดและไม่จำเป็นต้องผ่านโหนดรูท ดังนั้นหากแผนผังอินพุตเป็น −
ที่นี่ผลลัพธ์จะเป็น 32
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
กำหนดวิธีหนึ่งที่เรียกว่า Solve() ซึ่งจะใช้โหนด
-
ถ้าโหนดเป็นโมฆะหรือค่าของโหนดเป็น 0 ให้คืนค่า 0
-
ซ้าย :=สูงสุด 0 และแก้ (ซ้ายของโหนด)
-
right :=สูงสุดของ 0 และแก้ (ทางขวาของโหนด)
-
ans :=สูงสุดของ ans และ left + right + data ของโหนด
-
ส่งคืนข้อมูลโหนด + สูงสุดของซ้ายและขวา
-
จากเมธอดหลัก ให้ตั้งค่า ans :=-inf จากนั้นเรียก Solve(root) และคืนค่า ans
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
class TreeNode:
def __init__(self, data, left = None, right = None):
self.data = data
self.left = left
self.right = right
def insert(temp,data):
que = []
que.append(temp)
while (len(que)):
temp = que[0]
que.pop(0)
if (not temp.left):
if data is not None:
temp.left = TreeNode(data)
else:
temp.left = TreeNode(0)
break
else:
que.append(temp.left)
if (not temp.right):
if data is not None:
temp.right = TreeNode(data)
else:
temp.right = TreeNode(0)
break
else:
que.append(temp.right)
def make_tree(elements):
Tree = TreeNode(elements[0])
for element in elements[1:]:
insert(Tree, element)
return Tree
class Solution(object):
def maxPathSum(self, root):
self.ans = -float('inf')
self.solve(root)
return self.ans
def solve(self,node):
if not node or node.data == 0:
return 0
left = max(0,self.solve(node.left))
right = max(0,self.solve(node.right))
self.ans = max(self.ans,left+right+node.data)
return node.data + max(left,right)
ob = Solution()
root = make_tree([-10,9,10,None,None,15,7])
print(ob.maxPathSum(root)) อินพุต
[-10,9,10,None,None,15,7]
ผลลัพธ์
32
