BinaryTree_Leetcode_114. Flatten Binary Tree to Linked List [swift]

https://leetcode.com/problems/flatten-binary-tree-to-linked-list/description/?envType=study-plan-v2&envId=top-100-liked

 

문제접근

아이디어 1 - root를 pre-order순서로 순회한다. array같은곳에 append해서 순서대로 저장. array를 순회하며 flatten형태로 변환

아이디어 2 - root를 pre-order순서로 순회한다. left, right의 참조값을 지역 변수에 할당. left를 즉시 right에 할당. right는 후위를 방문 할 때 마지막으로 방문했던 node에 붙여준다.

 

아이디어 1은 구현하고, 읽기는 편하지만 여러모로 성능상 좋지 않아보인다.

그래서 아이디어2로 구현하였다.

그런데 문제에 in-place로 구현하라는 단서가 있긴 있었는데, 너무 밑에 적혀있었다..

Follow up: Can you flatten the tree in-place (with O(1) extra space)?

 

 

정답코드

class Solution {
    var lastVisitedNode: TreeNode? = nil

    func flatten(_ root: TreeNode?) {
        visit(root)
    }

    func visit(_ root: TreeNode?) {
        guard let root else { return }
        lastVisitedNode = root
        var lhs = root.left
        var rhs = root.right

        if let lhs {
            root.right = lhs
            visit(lhs)
            root.left = nil
        }

        if let rhs {
            lastVisitedNode?.right = rhs
            visit(rhs)
            lastVisitedNode?.left = nil
        }
    }
}