(Easy - DFS) Leetcode - 572. Subtree of Another Tree

이 문제는 트리가 두 개 주어집니다. 원래 트리의 구조 안에 서브 트리 구조와 같은 구조가 있는지 확인하는 문제입니다.

만약 서브 트리 구조와 같은 구조가 있어도 추가적인 노드가 붙어있으면 같은 구조가 아닙니다.

 

서브 트리의 root 노드와 같은 노드가 나올때까지 자식 노드들을 타고 갑니다.

만약 root 노드와 같은 노드를 찾았다면 그 구조가 같은지 확인해줍니다.

 

    bool isSameStructure(TreeNode* main, TreeNode* sub) {
        if (!main || !sub) // 두 노드 중 하나만 nullptr이거나 모두 nullptr인 경우
            return !main && !sub; // 두 노드 모두 nullptr인 경우엔 true 아니면 false 반환

        if (main->val == sub->val) // 만약 두 노드의 값이 같다면
        	// 자식 노드를 확인
            return isSameStructure(main->left, sub->left) && isSameStructure(main->right, sub->right);
        
        // 두 노드의 값이 다르면 false
        return false;
    }

위의 함수는 같은 구조를 가지고 있는지 확인하는 함수입니다.

if (!main || !sub) // 두 노드 중 하나만 nullptr이거나 모두 nullptr인 경우
	return !main && !sub; // 두 노드 모두 nullptr인 경우엔 true 아니면 false 반환

이 if statement 는 아래의 두 if statement를 하나로 줄인 것 입니다.

if (!main && !sub) // 만약 두 노드가 모두 nullptr이면
	return true; // 구조가 같으므로 true
if (!main || !sub) // 두 노드 중 하나만 nullptr이면
	return true; // 구조가 다르므로 false

 

이 구조를 확인하는 함수를 사용해 모든 노드에서 subtree와 같은 구조가 될 수 있는지 확인해 줍니다.

    bool isSubtree(TreeNode* root, TreeNode* subRoot) {
        if (!root) // root 노드가 없으면
            return false;
        
        // 현재 노드를 subtree의 root node로 하면 같은 구조를 같는지 확인
        if (isSameStructure(root, subRoot))
            return true;
        
        // 구조가 다르다면 왼쪽 자식과 오른쪽 자식 노드로 이동
        return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
    }

구조를 확인하는 함수에서는 subtree의 노드도 자식노드로 이동했지만 위의 함수에서는 현재 노드를 subtree의 root로 삼았을때 구조가 다르면 다른 노드를 subtree의 root 노드로 삼아야 하므로 원래 트리구조에서만 이동합니다.

 

전체 코드

/**
 * 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 isSameStructure(TreeNode* main, TreeNode* sub) {
        if (!main || !sub)
            return !main && !sub;

        if (main->val == sub->val)
            return isSameStructure(main->left, sub->left) && isSameStructure(main->right, sub->right);
        
        return false;
    }

    bool isSubtree(TreeNode* root, TreeNode* subRoot) {
        if (!root)
            return false;
        
        if (isSameStructure(root, subRoot))
            return true;
        
        return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
    }
};