Flatten Binary Tree to Linked List - LeetCode

Problem

1. input: 이진 트리의 루트 노드 root
2. output: 주어진 트리를 전위순회의 순서로 탐색한 결과를 연결리스트로 리턴
3. 오른쪽 자식으로 연결

ex)

• The number of nodes in the tree is in the range [0, 2000].
• 100 <= Node.val <= 100

Idea

주어진 트리를 재귀를 통해 전위 순회하며 동시에 오른쪽 자식으로 재배치 해주면 된다 → Sol1

Solution

1. 재귀

   • 원래 오른쪽 노드를 임시로 저장 → 오른쪽으로 재배치 하면서 덮어써짐으로
   • 왼쪽 자식부터 순회하고 각 노드를 오른쪽으로 재배치

   /**
    * Example:
    * var ti = TreeNode(5)
    * var v = ti.`val`
    * Definition for a binary tree node.
    * class TreeNode(var `val`: Int) {
    *     var left: TreeNode? = null
    *     var right: TreeNode? = null
    * }
    */
   class Solution {
       val head = TreeNode(0)
       var cursor = head
       fun flatten(root: TreeNode?): Unit {
           if (root == null) return
           val tmp = root!!.right // 원래 오른쪽 자식 노드 임시 저장
           cursor!!.right = root // 오른쪽 자식으로 노드 연결
           cursor = cursor!!.right // 다음 자리로 커서 이동
           flatten(root!!.left) // 왼쪽 자식 순회
           root!!.left = null
           flatten(tmp) // 오른쪽 자식 순회
       }
   }
   

   시간 복잡도:

   

Point