Exact Subtree
To solve this problem: https://leetcode.com/problems/subtree-of-another-tree/description/:
public class Solution
{
public bool IsSubtree(TreeNode s, TreeNode t)
{
if (ExactMatch(s, t)) return true;
return s != null && (IsSubtree(s.left, t) || IsSubtree(s.right, t));
}
private bool ExactMatch(TreeNode s, TreeNode t)
{
if (s == null && t == null) return true;
if (s == null || t == null) return false;
if (s.val != t.val) return false;
return ExactMatch(s.left, t.left) && ExactMatch(s.right, t.right);
}
}
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.What you want to do is to have two nested pre-order traversal functions: the inner function checks whether two tree are identical matches (notice the null checks in the beginning), the outermost function traverses all the nodes in s and checks whether the subtree rooted at that current node is an exact match with t. Time-complexity: O(|s| * |t|). Thanks, Marcelo
public class Solution
{
public bool IsSubtree(TreeNode s, TreeNode t)
{
if (ExactMatch(s, t)) return true;
return s != null && (IsSubtree(s.left, t) || IsSubtree(s.right, t));
}
private bool ExactMatch(TreeNode s, TreeNode t)
{
if (s == null && t == null) return true;
if (s == null || t == null) return false;
if (s.val != t.val) return false;
return ExactMatch(s.left, t.left) && ExactMatch(s.right, t.right);
}
}
Recursion rocks!
ReplyDeleteclass Solution {
private:
bool isEqual(const TreeNode* s, const TreeNode* t) {
if (s == t) return true;
if (s == nullptr || t == nullptr) return false;
return s->val == t->val && isEqual(s->left, t->left) && isEqual(s->right, t->right);
}
public:
bool isSubtree(TreeNode* s, TreeNode* t) {
if (s == t) return true;
if (s == nullptr || t == nullptr) return false;
return isEqual(s, t) || isSubtree(s->left, t) || isSubtree(s->right, t);
}
};