572.Subtree of Another Tree

Tags: [tree], [binary_tree], [same_tree], [inorder], [inorder_traversal], [stack]

Com: {f}

Hard: [###]

Link: https://leetcode.com/problems/subtree-of-another-tree/\#/description

Given two non-empty binary treessandt, check whether treethas exactly the same structure and node values with a subtree ofs. A subtree ofsis a tree consists of a node insand all of this node's descendants. The treescould 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.

Solution: Inorder Traversal

# 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 isSubtree(self, s, t):
        """
        :type s: TreeNode
        :type t: TreeNode
        :rtype: bool
        """
        if not s:
            return not t
        if not t:
            return not s

        return self.is_subtree_helper(s, t)

    def is_subtree_helper(self, s_root, t_root):
        # base case
        if not s_root:
            return not t_root

        if s_root.val == t_root.val and self.is_same_tree(s_root, t_root):
            return True

        return self.is_subtree_helper(s_root.left, t_root) or\
               self.is_subtree_helper(s_root.right, t_root)

    def is_same_tree(self, root1, root2):
        if not root1:
            return not root2
        if not root2:
            return not root1

        # inorder traversal for both tree.
        stack1 = []
        stack2 = []
        curr1 = root1
        curr2 = root2

        while curr1 or stack1:
            if curr1:
                # curr1 is not None
                # curr2 should not be None
                if not curr2:
                    return False

                stack1.append(curr1)
                curr1 = curr1.left

                stack2.append(curr2)
                curr2 = curr2.left
            else:
                # curr1 is None and stack1 is not empty
                # curr2 should be None and stack2 should not be empty
                if not (curr2 is None and len(stack2) > 0):
                    return False

                curr1 = stack1.pop()
                curr2 = stack2.pop()
                if curr1.val != curr2.val:
                    return False

                curr1 = curr1.right
                curr2 = curr2.right

        # curr1 is None and stack1 is empty
        # curr2 should be None and stack2 should be empty
        return not curr2 and not stack2

Revelation:

• When we use the inorder traversal(iterative), check the two trees, the main while loop condition is:

while curr1 or stack1:

• this means the curr1 is not None or stack1 is not empty, but it also means the curr1 and stack1 can be both not empty, so this is the reason why the following only check whether curr2 is not None or not, because at this point, the stack2 can be empty, and also can be not empty.

if curr1:
    if not curr2:
        return False

Note:

• Time complexity = O(n + m), n is the number of nodes in tree s, and m is the number of nodes in tree t.
• Space complexity = O(max(sh, th)), sh is the height of tree s, and th is the height of the tree t.