Subtree of Another Tree
Given two binary trees, write a function to check if the first tree is a subtree of the second tree. A subtree of a tree T is a tree S where the following conditions are true: (i) S is a subtree of T; (ii) There is a node N in T such that the subtree of N is identical to S; (iii) The subtree of N contains all the descendants of N.
Constraints:
- Both trees are non-empty
- The number of nodes in both trees will not exceed 200
Examples:
Input: [3,4,5,1,2] and [4,1,2]
Output: true
Explanation: Because the tree [4,1,2] is in the tree [3,4,5,1,2].
Solutions
Recursive Approach
The solution uses a recursive approach to check if the first tree is a subtree of the second tree. It defines a helper function isSameTree to check if two trees are identical. The main function checks if the current tree is the same as the target tree, and if not, it recursively checks the left and right subtrees.
class Solution {
public boolean isSubtree(TreeNode s, TreeNode t) {
boolean isSameTree(TreeNode s, TreeNode t) {
if (s == null && t == null) return true;
if (s == null || t == null) return false;
return s.val == t.val && isSameTree(s.left, t.left) && isSameTree(s.right, t.right);
}
if (s == null) return false;
if (isSameTree(s, t)) return true;
return isSubtree(s.left, t) || isSubtree(s.right, t);
}Follow-up:
How would you optimize the solution if the trees are very large?
