이진 트리가 제공된다고 가정합니다. 하위 트리에 이진 탐색 트리(BST)가 있는지 확인하고 가장 큰 BST의 합을 찾아야 합니다. 합계를 찾기 위해 해당 BST의 각 노드 값을 추가합니다. 합계 값을 출력으로 반환합니다.
따라서 입력이 다음과 같으면
그러면 출력은 12가 됩니다.
주어진 이진 트리의 BST는 -
노드의 합 =12.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- c :=0
- m :=null
- 값:=0
- recurse() 함수를 정의합니다. 이것은 node
- 를 취할 것입니다.
- 노드가 null이 아니면
- left_val :=recurse(노드의 왼쪽)
- right_val :=recurse(노드의 오른쪽)
- count :=음의 무한대
- if(node.left가 null 또는 node.left.val <=node.val과 동일) and((노드의 오른쪽이 null 또는 node.val <=node.right.val과 동일), then
- 카운트:=left_val + right_val + 1
- count> c이면
- c :=개수
- m :=노드
- 반환 횟수
- 0을 반환
- 노드가 null이 아니면
- calculate_sum() 함수를 정의합니다. 이것은 뿌리를 내릴 것입니다
- 루트가 null과 같지 않으면
- calculate_sum(루트 왼쪽)
- 값 :=값 + 루트 값
- calculate_sum(루트 오른쪽)
- 루트가 null과 같지 않으면
- 재귀(루트)
- calculate_sum(m)
- 반환 값
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
class TreeNode:
def __init__(self, val, left = None, right = None):
self.val = val
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
def solve(root):
c, m, value = 0, None, 0
def recurse(node):
if node:
nonlocal c, m
left_val = recurse(node.left)
right_val = recurse(node.right)
count = -float("inf")
if (node.left == None or node.left.val <= node.val) and (node.right == None or node.val <= node.right.val):
count = left_val + right_val + 1
if count > c:
c = count
m = node
return count
return 0
def calculate_sum(root):
nonlocal value
if root is not None:
calculate_sum(root.left)
value += root.val
calculate_sum(root.right)
recurse(root)
calculate_sum(m)
return value
tree = make_tree([1, 4, 6, 3, 5])
print(solve(tree)) 입력
tree = make_tree([1, 4, 6, 3, 5]) print(solve(tree))
출력
12