Algorithm
Problem Name: 572. 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.
Example 1:
Input: root = [3,4,5,1,2], subRoot = [4,1,2] Output: true
Example 2:
Input: root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2] Output: false
Constraints:
- The number of nodes in the
roottree is in the range[1, 2000]. - The number of nodes in the
subRoottree is in the range[1, 1000]. -104 <= root.val <= 104-104 <= subRoot.val <= 104
Code Examples
#1 Code Example with C Programming
Code -
C Programming
bool equal(struct TreeNode *node, struct TreeNode *t) {
if (!node && !t) return true;
if (!node || !t || node->val != t->val) return false;
return equal(node->left, t->left) && equal(node->right, t->right);
}
bool isSubtree(struct TreeNode* s, struct TreeNode* t) {
if (equal(s, t) ||
(s && isSubtree(s->left, t)) ||
(s && isSubtree(s->right, t))) return true;
return false;
}
Input
Output
#2 Code Example with C++ Programming
Code -
C++ Programming
class Solution {
public:
bool isSubtree(TreeNode* s, TreeNode* t) {
if(!s) return !t;
return isEqual(s, t) || isSubtree(s->left, t) || isSubtree(s->right, t);
}
bool isEqual(TreeNode* p, TreeNode* t){
if(!p || !t) return !p && !t;
return p->val == t->val && isEqual(p->left, t->left) && isEqual(p->right, t->right);
}
};
Input
Output
#3 Code Example with Java Programming
Code -
Java Programming
class Solution {
public boolean isSubtree(TreeNode root, TreeNode subRoot) {
if (root == null) {
return false;
}
if (isSubtreeHelper(root, subRoot)) {
return true;
}
return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
}
private boolean isSubtreeHelper(TreeNode root, TreeNode subRoot) {
if (root == null && subRoot == null) {
return true;
}
if (root == null || subRoot == null) {
return false;
}
if (root.val != subRoot.val) {
return false;
}
return isSubtreeHelper(root.left, subRoot.left) && isSubtreeHelper(root.right, subRoot.right);
}
}
Input
Output
#4 Code Example with Javascript Programming
Code -
Javascript Programming
const isSubtree = function(s, t) {
if (s == null) return false
if (isSame(s, t)) return true
return isSubtree(s.left, t) || isSubtree(s.right, t)
};
function isSame(s, t) {
if (s == null && t == null) return true
if (s == null || t == null) return false
if (s.val !== t.val) return false
return isSame(s.left, t.left) && isSame(s.right, t.right)
}
Input
Output
#5 Code Example with Python Programming
Code -
Python Programming
class Solution:
def isSubtree(self, s, t):
"""
:type s: TreeNode
:type t: TreeNode
:rtype: bool
"""
def traverse(node):
if not node: return "^"
return "$"+str(node.val)+"?"+traverse(node.left)+"@"+traverse(node.right)
return traverse(t) in traverse(s)
Input
Output
#6 Code Example with C# Programming
Code -
C# Programming
namespace LeetCode
{
public class _0572_SubtreeOfAnotherTree
{
public bool IsSubtree(TreeNode s, TreeNode t)
{
return Traverse(s, t);
}
private bool Traverse(TreeNode s, TreeNode t)
{
return s != null && (EqualTree(s, t) || Traverse(s.left, t) || Traverse(s.right, t));
}
private bool EqualTree(TreeNode s, TreeNode t)
{
if (s == null && t == null) return true;
if (s == null || t == null) return false;
return s.val == t.val && EqualTree(s.left, t.left) && EqualTree(s.right, t.right);
}
}
}
Input
Output