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

<解題>

1. 首先檢查 s 是否為空，如果是，則檢查 t 是否也為空，如果是，則返回 true，表示 t 是空樹也是 s 的子樹。
2. 用isSame(s, t)，判斷兩者是否相同，相同的話t就是s的子樹；若不相同，再來用遞迴方式看左子樹或右子樹是否有包含t

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

private boolean isSame(TreeNode t1, TreeNode t2) { 
  if (t1 == null && t2 == null) return true;
  if (t1 == null || t2 == null) return false;
  
  if (t1.val != t2.val) return false;
  return isSame(t1.left, t2.left) && isSame(t1.right, t2.right);
}
}

Time: O(mxn) Space: O(n)