Tree 문제를 Recursive 하게 풀 때 예시(leetcode #110)

저번 포스팅에서 대략적으로 Tree 문제를 크게 어떻게 풀어야 할지 두 가지 방법을 적어봤다.

그중 두 번째 방법인 Recursive 하게 풀어야 될 것 같을 때는 너무 어렵게 생각하지 말고, 머릿속으로 Tree를 타고 Leaf Node까지 내려가지 말고(머리가 핑핑 돌게 될 것이다) 쉽고 간단하게 풀면 된다고 했다.(아니 그게 뭔 개소립니까? 차라리 펀쿨섹하게 풀라하지?)

설명이 모호했던 것 같아서, 예시 문제와 함께 설명을 해보려 한다.

 

https://leetcode.com/problems/balanced-binary-tree/

Balanced Binary Tree - LeetCode

 

leetcode의 110번째 문제다.(Acceptance는 44%, Easy 난이도에 속함) 참고로 나는 알고리즘 문제를 풀 때 leetcode를 이용한다! 백준 등 다른 유명한 사이트도 있긴 하지만, 뭔가 외국 사이트니까 간지 나 보이고, 여기서 문제를 풀면 알고리즘 관련된 영어 단어도 공부할 수 있으니 좋은 것 같아서 leetcode를 선택했다.(leetcode에서 문제를 풀고, Accept이 되면 내 답안 코드를 Github에 바로바로 올리는 편이다. 지금까지 푼 다른 문제가 궁금하시다면 Home에 있는 내 Github를 참조하시길!)

 

문제를 간략히 설명하면, 주어진 Binary Tree가 Balanced Binary Tree 인지를 체크하는 것인데, Balanced Binary Tree란 문제에서

a binary tree in which the left and right subtrees of every node differ in height by no more than 1.

으로 정의하고 있다.(문제의 자세한 설명과 예시 트리가 링크에 있으니 좀 더 쉬운 이해를 위해 링크를 한 번 보고 오면 좋다! 트리를 직접 그리고 싶지만 여기서 어떻게 쉽게 그려야 할지 모르겠다)

 

Tree의 모든 Node가 Balanced Binary Tree여야 한다. 각각 노드가 조건을 만족을 해야 하고, 각 노드에서 체크해야 할 것(Balanced Binary Tree인지 체크)이 똑같기 때문에, 나는 뭔가 Recursive 하게 풀어야겠다고 큰 그림을 그렸다.

그리고 Recursive하게 풀어야겠다고 결정한 순간! 어렵게 생각하지 않는다.

저번 포스팅에 썼던 것처럼, 

1. 현재 노드에서 해야 할 것 생각해보기

2. 바로 left, right로 넘겨버리기

의 순서로 진행한다. 이렇게 하지 않고 머릿속으로 Node를 따라 내려가다 보면, 야밤에 숲 속에서 길을 잃은 듯한 느낌을 받을 수 있다.(여기가 어느 Node인지도 모르겠고, 내가 이 Node까지 어떻게 왔는지도 모르겠고....뭔가 같은 곳을 빙빙 도는 것 같고....)

 

다음은 저 순서를 적용한 나의 실제 해답이다.

/**
 * 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:
    bool isBalanced(TreeNode* root) {
        if(!root) return true;
        int l_height = get_height(root->left, 0);
        int r_height = get_height(root->right, 0);
        if(abs(l_height - r_height) > 1) return false;
        bool l = isBalanced(root->left);
        bool r = isBalanced(root->right); 
        if(l&&r) return true;
        else return false;
    }
    int get_height(TreeNode* root, int depth){
        if(!root) return depth;
        int l = 0, r = 0;
        l = get_height(root->left, depth+1);
        r = get_height(root->right, depth+1);
        return max(l, r);
    }
};

 

설명을 하자면, get_height()는 해당 노드의 깊이(height)를 return 하는 함수이다.

본 함수인 isBalanced()에서 먼저 해당 노드에서 해야 할 것을 생각해본다.(1. 노드가 nullptr인지? 2. Balanced Binary Tree를 만족하는지?) 그 후 해당 노드의 왼쪽, 오른쪽 서브 트리의 height를 구하고 그것을 이용해서 조건을 체크한다!

그러고 나서 

bool l = isBalanced(root->left);
bool r = isBalanced(root->right);

다음과 같이 left와 right를 넘겨버린다! 그 이후 '그럼 컴퓨터가 알아서 깔끔하게 도미노처럼 촤라라락 풀어주겠지...' 하고 쉽게 생각해버린다.

그리고 return을 해줄 때 어떻게, 무엇을 해줄지만 조금 더 고민하면 문제가 잘 풀릴 것이다.