[LeetCode] 110. Balanced Binary Tree

LeetCode - 110. Balanced Binary Tree 알고리즘 문제 풀이

분류

문제 링크 : https://leetcode.com/problems/balanced-binary-tree/

풀이

주어진 트리의 균형이 이루어지면 true, 이루어지지 않으면 false를 반환하는 문제이다.

트리의 균형이 맞추어지기 위한 조건은 좌측 서브트리와 우측 서브트리의 높이 차이가 1 이하인 경우이다.

---

좌측 서브트리와 우측 서브트리의 높이 차를 구해야한다는 것이 자명하므로, 특정 노드의 끝까지 탐색하면서 균형을 이루는지 검사해야 한다.

특정 서브트리로 진입하기 위해 전위순회(preorder)를 사용했는데, 사실 왼쪽 서브트리와 오른쪽 서브트리를 갖는 임의의 부모 노드 x에서 해주어야 할 역할이 각 서브 트리 높이 중 큰 값을 취하고 +1을 해주는 작업 뿐이라 DFS와 똑같다고 볼 수 있다.

여기까지만 구현해보면 아래와 같다. 하지만 이 경우에는 특정 depth에서 편향여부를 판별할 수 없다.

int preorder(TreeNode *root) {
    if (root == nullptr) {
        return 0;    
    }
    int L = preorder(root->left);
    int R = preorder(root->right);
    return max(L, R) + 1;
}

bool isBalanced(TreeNode* root) {
    if (root == nullptr) return true;

    int L = preorder(root->left);
    int R = preorder(root->right);
    return abs(L - R) <= 1;
}

Input : [1,1,1,1,null,null,1,1,null,null,1]
Output : false (AC)
Output : true (WA)

이 부분을 놓쳐서 3번 제출끝에 AC를 받았는데, 각 depth에서 균형이 깨지는 것을 판별하기 위해 현재 노드의 좌측 서브트리와 우측 서브트리를 isBalanced(TreeNode*) 함수로 전달하면 된다.

return abs(L - R) <= 1 && isBalanced(root->left) && isBalanced(root->right);

소스 코드

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int preorder(TreeNode *root) {
        if (root == nullptr) {
            return 0;    
        }
        int L = preorder(root->left);
        int R = preorder(root->right);
        return max(L, R) + 1;
    }
    
    bool isBalanced(TreeNode* root) {
        if (root == nullptr) return true;
        
        int L = preorder(root->left);
        int R = preorder(root->right);
        return abs(L - R) <= 1 && isBalanced(root->left) && isBalanced(root->right);
    }
};