Subtree of Another Tree
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.
Examples
Constraints
The number of nodes in the root tree is in the range [1, 2000].The number of nodes in the subRoot tree is in the range [1, 1000].-10^4 <= Node.val <= 10^4
Approach
We can traverse the `root` tree. For every node, we treat it as a potential root and check if the tree starting from this node is identical to `subRoot`. We can reuse the `isSameTree` logic. The base cases for the main function: if `subRoot` is null, it's always a subtree. If `root` is null but `subRoot` is not, it's false. Otherwise, check if they are the same tree, or recursively search in `root.left` and `root.right`.
Complexity Analysis
m is the number of nodes in root, n is the number of nodes in subRoot. In the worst case, we might need to check if the trees are the same starting at every node in root.
class Solution { public boolean isSubtree(TreeNode root, TreeNode subRoot) { if (subRoot == null) return true; if (root == null) return false; if (isSameTree(root, subRoot)) { return true; } return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot); } private boolean isSameTree(TreeNode p, TreeNode q) { if (p == null && q == null) return true; if (p == null || q == null || p.val != q.val) return false; return isSameTree(p.left, q.left) && isSameTree(p.right, q.right); }}