이진트리 균형 확인문제

                                    문제:
이진트리가 균형(height-balanced)인지 아닌지를 확인하라.

class TreeNode(var 'val': Int) {
    var left: TreeNode? = null,
    var right: TreeNode? = null
}

`val`은 두 노드사이에서 중복이 가능함
* BST가 아닌 Binary Tree이다.

                                    1. height balanced를 알아보려면 좌/우 노드의 높이 차이가 1이하 여야 한다.

                                    오답코드

class Solution {
    fun getHeight(root: TreeNode?): Int {
        if (root == null) {
            return 1
        }
        var leftHeight = 1
        var rightHeight = 1

        var leftTemp = root
        while (leftTemp != null) {
            leftTemp = leftTemp.left ?: break
            leftHeight++
        }

        var rightTemp = root
        while (rightTemp != null) {
            rightTemp = rightTemp.right ?: break
            rightHeight++

        }

        return maxOf(leftHeight, rightHeight)
    }
    fun isBalanced(root: TreeNode?): Boolean {
        var leftHeight = 0
        var rightHeight = 0
        root?.left?.let {
            leftHeight += getHeight(it)
        }

        root?.right?.let {
            rightHeight += getHeight(it)
        }

        return if (leftHeight > rightHeight) {
            leftHeight - rightHeight <= 1
        } else {
            rightHeight - leftHeight <= 1
        }
    }
}

                                    ✏️ 논리 수정하기

1. 자식에서 좌,우 대칭 여부를 확인해야한다.
2. recursive를 사용하면 좋을 것 같다.

                                    class Solution {
    fun getHeight(root: TreeNode?): Int {
        if (root == null) {
            return 0
        }

        val leftHeight = getHeight(root.left)
        val rightHeight = getHeight(root.right)
        return 1 + maxOf(leftHeight, rightHeight)
    }
    fun isBalanced(root: TreeNode?): Boolean {
        if (root == null) return true

        val leftHeight = getHeight(root.left)
        val rightHeight = getHeight(root.right)

        if (abs(leftHeight - rightHeight) > 1) {
            return false
        }

        return isBalanced(root.left) && isBalanced(root.right)
    }
}

                                    ✒️ 개선된 것
1. 잘못된 Height
getHeight에서 left는 왼쪽으로만 이동하고, right는 오른쪽으로만 이동했다.
아래 케이스 대응이 불가함

      1
    /   \
  2      3
        /  \
       4    5
        \
         6

1 leftHeight는 1, rightHeight는 3인데
기존 코드로는 1, 2로 되어서 차이가 1이므로 오답

2. abs를 사용하여 코드 길이 줄이기 - 기본적인 kotlin 모듈이 내장되어 있다.

3. recursive를 사용하여 모든 노드에 대하여 balanced 확인하기
- 기존 코드는 하나의 코드에서만 balnced 여부를 확인했었다.

                                    ⌚ 시간 복잡도 분석
해당 문제의 입력은 0~5000개의 노드
O(N^2)의 시간 복잡도.

1. 모든 노드의 높이 구할 때 O(N)
2. 각 노드가 balanced한지 체크할 때 O(N)

🛰️ 공간 복잡도 분석
재귀 호출: getHeight, isBalanced는 둘 다 재귀호출을 수행한다.
가장 깊은 경우 트리의 높이 만큼 스택 프레임이 쌓인다. O(h)
h는 평균적으로 logN(균형 트리), 최악의 경우 N까지 가능하다. (N은 노드 갯수)

O(log N) ~ O(N)

                                    class Solution {
    fun optCheck(root: TreeNode?): Int {
        if (root == null) return 0

        val left = optCheck(root.left)
        if (left == -1) return -1

        val right = optCheck(root.right)
        if (right == -1) return -1

        if (abs(left - right) > 1) return -1

        return 1 + maxOf(left, right)
    }

    fun isBalanced(root: TreeNode?): Boolean {
        return optCheck(root) != -1
    }
}

                                    ⭐ tip!
1. Height를 구할때는 1 + maxOf(left, right)패턴 기억하기