IT/자기계발 ( Leetcode )
2021-02-09] Convert BST to Greater Tree
Bell_bear
2021. 2. 9. 22:33
반응형
오늘의 문제:
이번에도 Tree 문제이다.
예시를 보면서 문제를 이해해 보자.
주어지는 BST root에서 가장 오른쪽의 값 부터 시작해서, 값을 더해 커지는 Tree를 만드는 것이 목표이다.
예시처럼 맨 오른쪽의 leaf node의 값인 8은 그대로고, 그 위의 root 7 -> 8+7= 15로 치환 되며,
계속 방문하며 파란색의 값으로 변경하고 이를 반환하면 된다.
우선 BFS,DFS 문제인 것을 알 수 있고, 이를 어떤 순서로 방문해야 하는지가 관건이다.
node의 오른쪽 -> 현재 node -> node의 왼쪽 순서로 방문하여 값을 변경 해주면 되겠다.
아래 코드를 보며 이해해보자.
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
def BFS(node: TreeNode):
if node == None: # Node가 비어있다면 끝
return
global bval
if node.right: # 오른쪽 -> 중간 -> 왼쪽 순서로 방문
BFS(node.right)
bval=bval+node.val # 가장 오른쪽부터 시작 node의 값을 더해주며, node.val에 저장
node.val=bval
if node.left:
BFS(node.left)
class Solution:
def bstToGst(self, root: TreeNode) -> TreeNode:
ans=root # 주어지는 값을 변경할 복사 Tree
global bval
bval=0 # 이전 값을 더하여 저장할 변수
BFS(ans)
return ans반응형