leetcode medium : flatten binary tree to linked list

https://leetcode.com/problems/flatten-binary-tree-to-linked-list/submissions/

Flatten Binary Tree to Linked List - LeetCode

 

일단은 그냥 naive하게 풀어봤다.

class Solution:
    def flatten(self, root: Optional[TreeNode]) -> None:
        if not root:
            return

        if not root.left and not root.right:
            return
        
        if not root.left:
            self.flatten(root.right)
        
        if not root.right:
            self.flatten(root.left)
            root.right = root.left
            root.left = None
            
        if root.left and root.right:
            self.flatten(root.left)
            self.flatten(root.right)
            
            left_end = root.left
            while left_end.right:
                left_end = left_end.right
            
            left_end.right = root.right
            root.right = root.left
            root.left = None

 

if문이 너무 많은 느낌이다.

 

썩 만족스럽진 않네

 

class Solution:
    def flatten(self, root: Optional[TreeNode]) -> None:
        if not root:
            return

        self.flatten(root.left)
        self.flatten(root.right)
        
        if root.left:
            left_end = root.left
            while left_end.right:
                left_end = left_end.right
            left_end.right = root.right
            root.right = root.left
            root.left = None

낫배드

 

어차피 preorder라서 root의 right에 root의 left를 flatten시킨걸 놓아야한다. left가 있으면 root.right에 할당하고 없으면 걍 root.right가 flatten된 상태로 내비둔다. 근데 left가 있을때 root.right에 할당하기 전에 root.left의 오른쪽 끝에 root.right를 붙여주어야한다. 그럼 끝!

 

시간복잡도는 얼마일까?

노드를 한번씩만 건드니까 O(N)일까?

공간복잡도는?

재귀를 사용하니까 O(logN)??

 

다른 사람 풀이를 봤는데 재귀 없이도 간단하게 풀수있다. 원리는 똑같다. 근데 이게 가능할줄은 몰랐네

class Solution:
    def flatten(self, root: Optional[TreeNode]) -> None:
        while root:
            if root.left:
                left_end = root.left
                while left_end.right:
                    left_end = left_end.right
                left_end.right = root.right
                root.right = root.left
                root.left = None
            
            root = root.right

 

일단 left subtree 끝자락에 right subtree를 붙인다. 그리고 left subtree를 right subtree로 만들고 right subtree에 대해 같은 작업을 수행한다. 내가 처음에 한게 bottom up식이라면 이건 top down식인듯? 미쳤네 그냥