Leetcode

Subtree of Another Tree

May 26, 2022 by aAshish

  • Time:O(mn), where m = |\text{nodes}| \in s and n = |\text{nodes}| \in t
  • Space:O(h), where h = \text{height(s)}

C++

 
class Solution {
 public:
  bool isSubtree(TreeNode* s, TreeNode* t) {
    if (!s)
      return false;
    if (isSameTree(s, t))
      return true;
    return isSubtree(s->left, t) || isSubtree(s->right, t);
  }

 private:
  bool isSameTree(TreeNode* p, TreeNode* q) {
    if (!p || !q)
      return p == q;
    return p->val == q->val &&
           isSameTree(p->left, q->left) &&
           isSameTree(p->right, q->right);
  }
};

JAVA

 
class Solution {
  public boolean isSubtree(TreeNode s, TreeNode t) {
    if (s == null)
      return false;
    if (isSameTree(s, t))
      return true;
    return isSubtree(s.left, t) || isSubtree(s.right, t);
  }

  private boolean isSameTree(TreeNode p, TreeNode q) {
    if (p == null || q == null)
      return p == q;
    return p.val == q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
  }
}