Subtree Check

Given two binary trees, check if the first tree is subtree of the second one. A subtree of a tree T is a tree S consisting of a node in T and all of its descendants in T.

解题思路

1. Find inorder and preorder traversals of T, store them in two auxiliary arrays inT[] and preT[].
2. Find inorder and preorder traversals of S, store them in two auxiliary arrays inS[] and preS[].
3. If inS[] is a subarray of inT[] and preS[] is a subarray preT[], then S is a subtree of T. Else not.
4. Time Complexity: Inorder and Preorder traversals of Binary Tree take O(n) time. The function strstr() can also be implemented in O(n) time using KMP string matching algorithm.

References

1. Check if a binary tree is subtree of another binary tree | Set 1
2. Check if a binary tree is subtree of another binary tree | Set 2