Leetcode - Subtree of Another Tree

Question

Given the roots of two binary trees root and subRoot, return true if there is a subtree of root with the same structure and node values of subRoot and false otherwise.

A subtree of a binary tree tree is a tree that consists of a node in tree and all of this node’s descendants. The tree tree could also be considered as a subtree of itself.

This is atree question.

Idea(s)

• Use the solution from Leetcode - Subtree of Another Tree to get a list of both tree nodes
• Use a subarray of array algorithm to check if the subtree array is a subarray of the main tree array
• You can also solve the “same tree” problem recursively
  • Check if p and q exist
  • If they are the same value
    • recursively check same tree on left and right children
  • Else return false
• Then you can dfs down the two trees until a subtree of the main tree is the same tree as the subtree using the sameTree function (ex here)

Solution