Version: Next

572.另一棵树的子树

给定两个非空二叉树 s 和 t，检验 s 中是否包含和 t 具有相同结构和节点值的子树。s 的一个子树包括 s 的一个节点和这个节点的所有子孙。s 也可以看做它自身的一棵子树。

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.

示例 1: 给定的树 s:

给定的树 t：

   4 
  / \
 1   2

返回 true，因为 t 与 s 的一个子树拥有相同的结构和节点值。

示例 2: 给定的树 s：

给定的树 t：

   4
  / \
 1   2

返回 false。

序列化

将树通过除了层序遍历以外的遍历方法，序列化为一个字符串，其中 null 节点也要被序列化打印，并且节点之间需要用 ! 符号进行分割（当然用其他符号也行）
大树序列化后与小树序列化结果进行 contains 操作，返回 contains 方法的结果即可

public class _572另一颗树的子树 {
    private static final String seperatorChar = "!";
    private static final String nullChar = "#";
    public StringBuilder sb = new StringBuilder();

    public boolean isSubtree(TreeNode s, TreeNode t) {
        // 后序遍历 序列化
        String treeStrS = getTreeStr(s);
        String treeStrT = getTreeStr(t);

        System.out.println("treeStrS = " + treeStrS);
        System.out.println("treeStrT = " + treeStrT);

        return treeStrS.contains(treeStrT);
    }

    private void visit(TreeNode node) {
        // 后序遍历
        if (node.left != null) visit(node.left);
        else sb.append(nullChar).append(seperatorChar);

        if (node.right != null) visit(node.right);
        else sb.append(nullChar).append(seperatorChar);

        sb.append(node.val).append(seperatorChar);
    }

    private String getTreeStr(TreeNode node) {
        visit(node);
        String treeStr = sb.toString();
        sb.delete(0,sb.length()); // 清空 sb
        return treeStr;
    }

    public static void main(String[] args) {
        TreeNode n1 = new TreeNode(1);
        TreeNode n2 = new TreeNode(2);
        TreeNode n3 = new TreeNode(3);

        n1.left = n2;
        n1.right = n3;

        _572另一颗树的子树 obj = new _572另一颗树的子树();
        boolean isSubtree = obj.isSubtree(n2, n1);
        System.out.println("isSubtree = " + isSubtree);
    }
}

运行结果

treeStrS = #!#!2!
treeStrT = #!#!2!#!#!3!1!
isSubtree = false

572.另一棵树的子树#

序列化#

572.另一棵树的子树

序列化