-
2021-02-09] Convert BST to Greater TreeIT/자기계발 ( Leetcode ) 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
반응형'IT > 자기계발 ( Leetcode )' 카테고리의 다른 글
2021-02-22] Longest Word in Dictionary through Deleting (0) 2021.02.22 2021-02-07] Shortest Distance to a Character (0) 2021.02.08 2021-02-04] Longest Harmonious Subsequence (0) 2021.02.04 2021-02-03] Linked List Cycle (0) 2021.02.03 2021-02-02] Trim a Binary Search Tree (0) 2021.02.03