Subtree of Another Tree

Problem Id: 572 Difficulty: Easy Tag: Tree


Intuition

We could get the preorder of each tree and test if preorder of t is a substring of preorder of s.

Solution


# 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: TreeNode, t: TreeNode) -> bool:
        preorder_s = []
        preorder_t = []
        self._preorder(s, preorder_s)
        self._preorder(t, preorder_t)
        st = self._str(preorder_t)
        ss = self._str(preorder_s)
        print(ss, st)
        return st in ss

    def _str(self, order):
        return ''.join([str(v) for v in order])

    def _preorder(self, node, order):
        if node is None:
            return
        order.append('(')
        order.append(str(node.val))
        self._preorder(node.left, order)
        self._preorder(node.right, order)
        order.append(')')