_572. Subtree of Another Tree.md

572. Subtree of Another Tree

All prompts are owned by LeetCode. To view the prompt, click the title link above.

Back to top

---

First completed : June 03, 2024

Last updated : July 01, 2024

---

Related Topics : Tree, Depth-First Search, String Matching, Binary Tree, Hash Function

Acceptance Rate : 49.13 %

---

Solutions

• e572 v2 ideal.py
• e572.py

Python

e572 v2 ideal.py

# Very fast (98%+) damn
# Stringification is niceeeeeee

# 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:
        def getString(node: Optional[TreeNode]) -> str:
            if not node :
                return '_'
            
            return "-" + str(node.val) + "-" + getString(node.left) + getString(node.right)
        
        rootStr = getString(root)
        subStr = getString(subRoot)

        return subStr in rootStr

e572.py

# A bit on the slower half of runtimes but workssss :l

# 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:
        def findPotentialStarts(node: Optional[TreeNode], val) -> [] :
            if not node:
                return []
            
            output = []
            if node.val == val :
                output.append(node)
            
            return output + findPotentialStarts(node.left, val) + findPotentialStarts(node.right, val)
        
        def checkCase(node: Optional[TreeNode], subNode: Optional[TreeNode]) -> bool :
            if ((node is None) ^ (subNode is None)) :
                return False

            if not node and not subNode :
                return True

            return node.val == subNode.val and checkCase(node.left, subNode.left) and checkCase(node.right, subNode.right)

        check = findPotentialStarts(root, subRoot.val)

        for node in check :
            if checkCase(node, subRoot) :
                return True
        
        return False