Leetcode - 572. Subtree of Another Tree

문제

root로 주어진 트리에 subRoot로 주어진 sub트리가 존재하는지 확인. 있다면 True, 없다면 false. subRoot의 서브트리와 완전히 동일해야함 아래 예시 참고.

Input: root = [3,4,5,1,2], subRoot = [4,1,2]
Output: true

Input: root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]
Output: false

아디이어

• 대부분의 트리문제는 재귀함수 형태로 푼다.
• 현재 주어진 r, s트리의 val이 동일하면 r->left와 r->left 에 대한 재귀 호출, 그리고 r->right와 r->right 에 대한 재귀 호출. 모든게 true이면 r, s는 동일한 트리이다. -> is_same()함수
• 만약 is_same 이 false인 경우 어떻게 처리할지를 처리하는게 어려웠음.
  • 하나의 재귀함수에서 모든 동작을 구현하기는 어렵고 두개의 재귀함수를 써야함.
  • root->left 에 가서 동일한 동작을 한번 더 수행, 그리고 root->right에서도 마찬가지. 둘중 하나만 true가 되어도 전체 답은 true가 되어야하기 때문에, || 조건으로 두 함수를 호출한다.

풀이

class Solution {
public:
    bool is_same(TreeNode* r, TreeNode* s) {
        /* base case */
        if (!r && s)
            return false;
        if (r && !s)
            return false;
        if (!r && !s)
            return true;
        
        return r->val == s->val && is_same(r->left, s->left) && is_same(r->right, s->right);
    }
    bool isSubtree(TreeNode* root, TreeNode* subRoot) {
        if (!root)
            return false;
        if (is_same(root, subRoot))
            return true;
        return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
    }
};

추가로 is_same함수에서 base case부분의 논리구조가 복잡하므로 코드를 더 단순화 시켜보자.

        if (!r && s)
            return false;
        if (r && !s)
            return false;
        if (!r && !s)
            return true;

밴다이어 그램을 그려보면

r && s 인 부분을 제외한 경우에만 해당하므로 -> if (!r || !s) 이렇게 표현할수 있다. 이 조건일때, true/ false를 구분하면 된다.

!r && !s 일때만 true이고 그 외의 경우는 false이므로 !r && !s 를 그대로 리턴. 아래와 같이 논리 식을 단순화 시킬 수 있다.

        if (!r || !s)
            return !r && !s;