Subtree of another tree#

Levels: level-3

Data structures: tree

Practice Link#

Description#

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.

Examples#

 1
 2Given tree s:
 3
 4     3
 5    / \
 6   4   5
 7  / \
 8 1   2
 9
10Given tree t:
11   4
12  / \
13 1   2
14
15 Output: true

 1Given tree s:
 2
 3     3
 4    / \
 5   4   5
 6  / \
 7 1   2
 8    /
 9   0
10
11Given tree t:
12   4
13  / \
14 1   2
15
16Output: false

Python Solution#

 1class TreeNode(object):
 2    def __init__(self, x):
 3        self.val = x
 4        self.left = None
 5        self.right = None
 6
 7
 8class Solution(object):
 9    def isSubtree(self, s, t):
10        """
11        :type s: TreeNode
12        :type t: TreeNode
13        :rtype: bool
14        """
15        def convert(p):
16            return "^" + str(p.val) + "#" + convert(p.left) + convert(
17                p.right) if p else "$"
18
19        return convert(t) in convert(s)