문제 링크 (opens new window)

문제 설명

1. 이진트리 - 자식 요소가 두개 이하인 트리
2. 전위 순회: 루트 - 왼쪽 - 오른쪽 순서
3. 중위 순회: 왼쪽 - 루트 - 오른쪽 순서
4. 후위 순회: 왼쪽 - 오른쪽 - 루트 순서
5. 문제 풀이에서는 오른쪽 - 루트 - 왼쪽 순서로 순회하는 독특한 방법으로 처리
6. 순회하는 동안 배열에 값 추가하고 나중에 노드끼리 값 바인딩

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public var val: Int
 *     public var left: TreeNode?
 *     public var right: TreeNode?
 *     public init() { self.val = 0; self.left = nil; self.right = nil; }
 *     public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
 *     public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
 *         self.val = val
 *         self.left = left
 *         self.right = right
 *     }
 * }
 */
class Solution {
    private var nodeValues: [Int] = []
    // 제일 왼쪽에 있는 값을 리턴해야됨
    private func order(_ current: TreeNode?) {
        guard let current else { return }
        order(current.right)
        nodeValues.append(current.val)
        order(current.left)
    }

    private func assignValueOrder(_ current: TreeNode?) {
        guard let current else { return }
        assignValueOrder(current.right)
        current.val = nodeValues.last!
        _ = nodeValues.removeLast()
        assignValueOrder(current.left)
    }
    func bstToGst(_ root: TreeNode?) -> TreeNode? {
        order(root)
        for i in 0..<nodeValues.count - 1 {
            nodeValues[i+1] = nodeValues[i+1] + nodeValues[i]
        }
        nodeValues = nodeValues.reversed()
        assignValueOrder(root)
        return root
    }
}