문제 설명
Given the root of a Binary Search Tree (BST), convert it to a Greater Tree such that every key of the original BST is changed to the original key plus sum of all keys greater than the original key in BST.
As a reminder, a binary search tree is a tree that satisfies these constraints:
- The left subtree of a node contains only nodes with keys less than the node’s key.
- The right subtree of a node contains only nodes with keys greater than the node’s key.
- Both the left and right subtrees must also be binary search trees.
- Note: This question is the same as 538: https://leetcode.com/problems/convert-bst-to-greater-tree/
Note: A leaf is a node with no children.
Example 1:
Input: root = [4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
Output: [30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]
Example 2:
Input: root = [0,null,1]
Output: [1,null,1]
Example 3:
Input: root = [1,0,2]
Output: [3,3,2]
Example 4:
Input: root = [3,2,4,1]
Output: [7,9,4,10]
Constraints:
- The number of nodes in the tree is in the range [1, 100].
- 0 <= Node.val <= 100
- All the values in the tree are unique.
- root is guaranteed to be a valid binary search tree.
문제풀이
문제를 이해하는데 오래걸렸다.. 정확히 어떠한 프로세스를 원하는지에 대해서 파악이 오래걸렸는데 DFS로 접근이 떠올랐다.
-
오른쪽 노드가 계속 존재할 경우는 오른쪽 노드가 끝날때까지 상위 노드의 값을 계속 전달해주어야한다.
-
오른쪽 노드가 탐색 중 존재 하지 않을경우 상위 노드의 값을 더한 뒤 return 한다.
-
오른쪽 노드 탐색이 모두 끝난 뒤 자신의 val 값이 업데이트 되어있을 것이고 왼쪽 노드가 존재한다면 업데이트 된 자신의 val을 왼쪽 노드에게 넘겨 준다.
-
왼쪽 노드는 위 순서부터 똑같이 반복하게 된다.
class Solution {
func DFS(_ node: TreeNode?, _ carrier: Int) -> Int {
guard let node = node else { return 0 }
if let rightNode = node.right {
node.val += DFS(rightNode, carrier)
} else {
node.val += carrier
}
if let leftNode = node.left { return DFS(leftNode, node.val) }
return node.val
}
func bstToGst(_ root: TreeNode?) -> TreeNode? {
guard let root = root else { return nil }
DFS(root, 0)
return root
}
}
참고 : https://leetcode.com/problems/binary-search-tree-to-greater-sum-tree/submissions/