Python에서 트리의 인접하지 않은 노드의 최대 합을 찾는 프로그램

<시간/>

이진 트리가 있다고 가정하고 부모와 자식이 인접할 수 없는 두 값이 주어지면 얻을 수 있는 값의 최대 합을 찾아야 합니다.

따라서 입력이 다음과 같으면

10, 4, 3이 서로 인접하지 않으므로 출력은 17이 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

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)