Skip to main content

Subtree of Another Tree

Question​

None

Example 1
Input: 
Tree 1: 
       3
      / \
     4   5
    / \
   1   2

Tree 2: 
     4 
    / \
   1   2

Output: true

Solution​

all//Subtree of Another Tree.py


# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    def isSubtree(self, s, t):
        if not s and not t:
            return True
        if not s or not t:
            return False
        return self.isSameTree(s, t) or self.isSubtree(s.left, t) or self.isSubtree(s.right, t)

    def isSameTree(self, s, t):
        if not s and not t:
            return True
        if not s or not t:
            return False
        if s.val != t.val:
            return False
        return self.isSameTree(s.left, t.left) and self.isSameTree(s.right, t.right)