Problem: Given two non-empty binary trees s and t, check whether tree t has exactly the same structure and node values with a subtree of s. A subtree of s is a tree consists of a node in s and all of this node's descendants. The tree s could also be considered as a subtree of itself.
Example:
Given tree s:
3
/ \
4 5
/ \
1 2Given tree t:
4 / \ 1 2
Return true, because t has the same structure and node values with a subtree of s.
Given tree s:
3
/ \
4 5
/ \
1 2
/
0Given tree t:
4 / \ 1 2
Return false.
Approach: We use preorder traversal here. While doing preorder traversal on s whenever we see value at current node of s and value of root of t are same, we check if the tree started from current node of s and t are same or not. If yes, we return true otherwise we continue with our preorder traversal.
Implementation in C#:
public bool IsSubtree(TreeNode s, TreeNode t)
{
if (s == null)
{
return false;
}
if (s.val == t.val)
{
if (this.AreEqual(s, t))
{
return true;
}
}
return this.IsSubtree(s.left, t) || this.IsSubtree(s.right, t);
}
private bool AreEqual(TreeNode t1, TreeNode t2)
{
if (t1 == null && t2 == null)
{
return true;
}
if (t1 == null || t2 == null)
{
return false;
}
return t1.val == t2.val && this.AreEqual(t1.left, t2.left) && this.AreEqual(t1.right, t2.right);
}
Complexity: O(m * n)
No comments:
Post a Comment