将树序列化为字符串,空节点用符号表示,这样可以唯一的表示一棵树。
用list记录所有子树的序列化,和目标树比较。
List<String> list = new ArrayList<>();
public boolean isSubtree(TreeNode s, TreeNode t) {
helper(s);
helper(t);
String tt = list.get(list.size()-1);
for (int i = 0;i<list.size()-1;i++) {
if (list.get(i).equals(tt)) return true;
}
return false;
}
public String helper(TreeNode root)
{
StringBuilder cur = new StringBuilder();
if (root==null)
{
cur.append("#");
return new String(cur);
}
cur.append(root.val);
cur.append(helper(root.left));
cur.append(helper(root.right));
String s = new String(cur);
list.add(s);
return s;
}
LeetCode上还有更好地答案,是递归地判断每个节点的值是不是相等,也很好理解。
上边这种做法是一个大类的做法,就是每个节点都递归地构建一个变量,一般子树问题会经常用到