Balanced Binary Tree

풀이

또귀임
재귀 그냥 죽여버리고 싶음
근데 공부해야댐

그래픽스에서 재귀 오지게 씀 ㅠㅠ

class Solution {
public:

    int height(TreeNode* node) {

        if (node == nullptr) {
            return 0;
        }

        int left = height(node->left);

        if (left == -1) {
            return -1;
        }

        int right = height(node->right);

        if (right == -1) {
            return -1;
        }

        if (abs(left - right) > 1) {
            return -1;
        }

        return max(left, right) + 1;
    }

    bool isBalanced(TreeNode* root) {
        return height(root) != -1;
    }
};

1. 

위 경우를 먼저 살펴보자

root = 1
stack = [1]
->left ~ 4

root = 3L
stack = [1, 2L, 3L]
->left = 4L

root = 4L
stack = [1, 2L, 3L, 4L] //L = 부모 기준 왼쪽노드
->left = nullptr, 0
->right = nullptr, 0
return max(0,0) + 1

root = 3L
stack = [1, 2L, 3L]
->left = 1
->right = 4R

root = 4R
stack = [1, 2L, 3L, 4R]
->left = nullptr, 0
->right = nullptr, 0
return max(0,0) + 1

root = 3L
stack = [1, 2L, 3L]
->left = 1
->right = 1
return max(1,1) + 1

이 과정을 쭉 이어나가면 root가 1일때 왼쪽 노드의 깊이가 3이라는게 구해진다.

하지만 2R로 넘어가면,
1이 반환이 되고,
root가 1일때 오른쪽 노드의 깊이가 1이 된다.

따라서 두 방향의 깊이의 차가 1보다 크므로 이는 불균형 이진트리가 된다.

2. 

이때 1번에서 살펴본 과정을 반복하면 root가 2일때
왼쪽의 깊이는 2, 오른쪽은 0이 되고
두 깊이의 차가 1보다 크므로, -1이 반환된다

!!!!!! 이때 -1이 반환되는 이유는
미리 값을 걸러내기 위함으로

if (left == -1) 
{
    return -1;
}

if (right == -1) 
{
    return -1;
}

이런 코드가 없으면
abs(-1 - 0) + 1 = 2가 되어 불균형 이진트리 임에도 불구하고
이상한 깊이가 반환되게 됨

그러므로 -1이라는 값은 중요!

사실 -1말고 -10000000해도 됨