Subtree of Another Tree

Question

Given two non-empty binary trees s and t, check whether tree t has exactly the same structure and node values with a subtree of s. A subtree of s is a tree consists of a node in s and all of this node's descendants. The tree s could also be considered as a subtree of itself.

Example 1: Given tree s:

     3
    / \
   4   5
  / \
 1   2

Given tree t:

   4 
  / \
 1   2

Return true, because t has the same structure and node values with a subtree of s.

Example 2: Given tree s:

     3
    / \
   4   5
  / \
 1   2
    /
   0

Given tree t:

   4
  / \
 1   2

Return false.

Tags

• Tree

Thought

Two approaches:

• Traversal through the two trees and compare each node one by one
• Generate the string based on the structure and the value of the tree and compare two strings

The implementations of the two approaches are below.

For the first approach, use recursion to make the traversal easier.

For the second approach, recursion is also necessary. Another important notice is that split the values between different nodes to when generating the string.

Code

Without string

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

class Solution(object):
    def helper(self, s, t):
        if s is None and t is None:
            return True
        elif (s is None) != (t is None):
            return False
        elif s.val != t.val:
            return False
        else:
            return self.helper(s.left, t.left) and self.helper(s.right, t.right)


    def isSubtree(self, s, t):
        """
        :type s: TreeNode
        :type t: TreeNode
        :rtype: bool
        """
        if s is None or t is None:
            return False
        return self.helper(s, t) or self.isSubtree(s.left, t) or self.isSubtree(s.right, t)

with string

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

class Solution(object):
    def traversal(self, node):
        """
        traversal of pre-order
        """
        if node is None:
            return '$'
        return '^' + str(node.val)  + '#' + self.traversal(node.left) + '#' + self.traversal(node.right)

    def isSubtree(self, s, t):
        """
        :type s: TreeNode
        :type t: TreeNode
        :rtype: bool
        """
        return self.traversal(t) in self.traversal(s)