[leetcode 1382] Balance a Binary Search Tree

1382. Balance a Binary Search Tree

https://leetcode.com/problems/balance-a-binary-search-tree/

해결 과정

• 입력된 TreeNode 를 inorderTraverse (중위순회) 하면서 정렬된 리스트를 먼저 만든다.
  • 탈출조건: 노드가 null일 때
• 중간 idx의 노드를 root로 하고, root.left 와 root.right 에 각각 (시작idx, 중간idx-1) 와 (중간idx+1, 마지막idx) 를 파라미터로 재귀를 호출하며 Balancing이 맞는 트리를 만든다.
  • 탈출조건: 시작idx 값이 마지막idx 값보다 클 때
  • 시작idx == 마지막idx 일 때는 왼쪽, 오른쪽 노드가 null인 root

코드

class Solution {
    var sortedArr: MutableList<TreeNode> = mutableListOf()
    
    fun balanceBST(root: TreeNode?): TreeNode? {
        inorder(root)
        return makeBalanceBST(0, sortedArr.size -1)
    }
    
    private fun inorder(root: TreeNode?) {
        if(null == root) return
        
        inorder(root.left)
        sortedArr.add(root)
        inorder(root.right)
    }
    
    private fun makeBalanceBST(startIdx: Int, endIdx: Int) : TreeNode? {
        if(startIdx > endIdx) return null
        
        val mid = (startIdx + endIdx) / 2
        val root = sortedArr[mid]
        root.left = makeBalanceBST(startIdx, mid-1)
        root.right = makeBalanceBST(mid+1, endIdx)
        return root
    }
}

배운 점

BST 를 inorder 순회하면, 오름차순 정렬된 리스트를 얻을 수 있다.

(* 왼쪽 서브 트리 < 루트 값 < 오른쪽 서브 트리)