[Leetcode] 572. Subtree of Another Tree 문제 풀이

https://leetcode.com/problems/subtree-of-another-tree/

Subtree of Another Tree - LeetCode

 

문제 내용

tree에서 subtree가 있는지 검사하는 문제

 

Example 1:

예제1번 그림

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

Output: true

 

문제 풀이

tree가 일치하는 지 매칭하기 위해 dfs탐색으로 풀었다.

먼저 subroot의 값이 매칭되는 부분을 찾고 같이 right, left 로 검사하였다.

매칭이 안된다고 false로 하면 안된다.

그 다음 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 matching(TreeNode* root, TreeNode* subRoot) {
        if (root == nullptr || subRoot == nullptr)
            return root == subRoot;
        
        if (root->val != subRoot->val)
            return false;
        
        return matching(root->left, subRoot->left) && matching(root->right, subRoot->right);
    }
    
    bool isSubtree(TreeNode* root, TreeNode* subRoot) {
        if (root == nullptr)
            return false;
        
        if (root->val == subRoot->val) {
            if (matching(root, subRoot))
                return true;
        }
            
        return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
    }
};