Subtree of Another Tree()

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

Given the roots of two binary trees root and subRoot, return true if there is a subtree of root with the same structure and node values of subRoot and false otherwise.

A subtree of a binary tree tree is a tree that consists of a node in tree and all of this node's descendants. The tree tree could also be considered as a subtree of itself.

 

Example 1:

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

Example 2:

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

 

Constraints:

• The number of nodes in the root tree is in the range [1, 2000].
• The number of nodes in the subRoot tree is in the range [1, 1000].
• -104 <= root.val <= 104
• -104 <= subRoot.val <= 104

Daily code 이번엔 Tree구조로 Come back 해봤다.

 

욥욥..!

 

1. Python

겁나 어거지로 풀긴했다.

근데 좀 찝찝하긴 하다. BFS는 솔직히 머릿속에 빡 떠오르는데 아직 DFS는 잘 떠오르지 않는다.

그래서 BFS 점철로 풀었다 ㅎㅎ...

DFS , in/pre/post order도 거의 자동으로 머릿속에 구현될 정도로 좀 익숙해질 필요가 있다.

# 핵 어거지로 풀긴했다. 무한 BFS 돌리기
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
        # root 기준 traversal을 돌면서 subRoot을 찾는다.
        # Traversal의 문제.. 
        def bfs(node1,node2) -> bool :
            q1 = deque([node1])
            q2 = deque([node2])
            while q1 or q2 :
                if (not q1 and q2) or (not q2 and q1) : return False
                temp1 = q1.popleft()
                temp2 = q2.popleft()
                if temp1.val != temp2.val : return False
                if (temp1.left and not temp2.left) or (not temp1.left and temp2.left): return False
                if (temp1.right and not temp2.right) or (not temp1.right and temp2.right): return False

                if temp1.left : q1.append(temp1.left)
                if temp2.left : q2.append(temp2.left)
                if temp1.right : q1.append(temp1.right)
                if temp2.right : q2.append(temp2.right)
            return True
        
        q = deque([root])
        while q:
            temp = q.popleft()
            if temp.val == subRoot.val:
                if bfs(temp,subRoot): return True
            if temp.left : q.append(temp.left)
            if temp.right : q.append(temp.right)
        return False

누누히 느끼지만, 코딩은 기세다. 할 수 있다고 마음먹으면 어케든 된다..!

(단, 원래 풀 수 있는 난이도였다는 가정하에 ㅎㅎ)

 

가독성 정리한 깔끔한 코드는 아래와 같다.

# 가독성 개선
class Solution:
    def same(self,x1: Optional[TreeNode],x2: Optional[TreeNode])->bool:
        if not x1 and not x2:
            return True
        if not x1 or not x2:
            return False
        return x1.val == x2.val and self.same(x1.left,x2.left) and self.same(x1.right,x2.right)
        


    def isSubtree(self, r: Optional[TreeNode], sr: Optional[TreeNode]) -> bool:
        if r is None:
            return False
        if self.same(r,sr):
            return True
        return self.isSubtree(r.left,sr) or self.isSubtree(r.right,sr)

 

 

2. C

그리고 C로도 풀어보기! 특이하게 C Array로 Queue를 구현해보았다..!

# C with queue -> C 로 queue 구현하기 C queue C 큐
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
bool helper(struct TreeNode* node1, struct TreeNode* node2){
    if(!node1 && !node2) return true;
    if((!node1 && node2)||(node1 && !node2)||(node1->val != node2->val)) return false;
    return helper(node1->left,node2->left) && helper(node1->right,node2->right);
}
bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot) {
    int front = 0 , rear = 0;
    struct TreeNode* queue[2001];
    queue[rear++] = root;
    while(front < rear){
        struct TreeNode* temp = queue[front++];
        if(helper(temp,subRoot)) return true;
        if(temp->left) queue[rear++] = temp->left;
        if(temp->right) queue[rear++] = temp->right;
    }
    return false;
}