[LeetCode#1038] Binary Search Tree to Greater Sum Tree

❒ Description

---

날짜	2024.09.25 (수)
레벨	Medium
제목	Binary Search Tree to Greater Sum Tree
링크	https://leetcode.com/problems/binary-search-tree-to-greater-sum-tree/description/
자료구조	BST

 

 

 

 

 

❒ 문제 분석 

---

BST

1. 누적 합을 관리해 줄 변수(accumulate)가 필요하다. 
2. 우선 주어진 트리에서 값이 가장 큰 노드를 찾아야 한다. (오른쪽 서브트리를 탐색)
3. accumulate에 현재 노드의 값을 갱신해준다. (덧셈)
4. 현재 노드의 왼쪽 서브트리를 탐색한다.
5. 2~3번 과정을 반복한다.

 

위 그림에서 작업 순서는 9 > 7 > 6 > 5 > 4 > 3 > 2 > 1 > 0 이 된다.

 

 

 

 

 

❒ Solution

---

int acc = 0;
public TreeNode bstToGst(TreeNode root) {
    if (root != null) {
        bstToGst(root.right); // 최초에 가장 큰 노드의 값까지 재귀
        acc += root.val;
        root.val = acc;
        bstToGst(root.left);
    }
    return root;
}

 

 

 

 

 

---