Интуитивное объяснение решения «Поддерево другого дерева»

В этой статье мы пройдем интуитивное объяснение поддерева другого решения дерева.

Постановка задачи

Учитывая, что у нас есть корневые узлы двух бинарных деревьев, а именно «root» и «subRoot», наша задача состоит в том, чтобы определить, существует ли поддерево внутри «root», которое отражает структуру и значения узлов «subRoot». Если такое поддерево существует, мы вернем true; в противном случае мы вернем false.

Следует отметить, что поддеревом бинарного дерева называется дерево, образованное конкретным узлом и всеми его последующими потомками. Дерево также рассматривается как поддерево самого себя.

Код Python

class Solution:
    def isSubtree(self, root: Optional[TreeNode], 
                        subRoot: Optional[TreeNode]) -> bool:
        # If subRoot is None then its a subtree of tree
        if not subRoot:
            return True
        
        # If root is None, there can't be a subtree for it
        if not root:
            return False
        
        # If the entire tree rooted at root matches subRoot, return True
        if self.sameTree(root, subRoot):
            return True
        
        # Recursively check if subRoot is a subtree of the right 
        # or left subtrees of root
        return (self.isSubtree(root.right, subRoot) or
                self.isSubtree(root.left, subRoot))

    def sameTree(self, root1, root2):
        # If both roots are None, then they are same tree
        if not root1 and not root2:
            return True
        
        # If one root is None while the other is not, they cannot be 
        # the same tree
        elif not root1 and root2:
            return False
        elif root1 and not root2:
            return False
        else:
            # Check if values of the current nodes match and recursively 
            # check left and right subtrees
            return all([root1.val == root2.val,
                        self.sameTree(root1.left, root2.left),
                        self.sameTree(root1.right, root2.right)])

Пошаговое объяснение

Если вам понравилось объяснение, следуйте за мной, чтобы узнать больше! Не стесняйтесь оставлять свои комментарии, если у вас есть какие-либо вопросы или предложения.

Ссылки

[1] Leetcode: https://leetcode.com/problems/subtree-of-another-tree/