【572】另一个树的子树

题目：

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

代码思想:

分两步，第一步，先在父树中找到子树的根节点，再分别比较父树和子树的左孩子和右孩子，递归的终止条件是：

• 如果父树节点和子树节点均为空，则是子树
• 如果两者其一为空，另一不为空，则返回false

子树的左孩子和右孩子都需要满足这两个条件才是子树，否则不是。

代码实现：

public boolean isSubtree(TreeNode s, TreeNode t) {
        if (s == null && t == null) return true;
        if (s == null || t == null) return false;
        if (s.val == t.val) {   
         //寻找根节点
            return isEqual(s, t) || isSubtree(s.left, t) || isSubtree(s.right, t);   
        }
        return isSubtree(s.left, t) || isSubtree(s.right, t);
    }

    public boolean isEqual(TreeNode s, TreeNode t) {
        if (s == null && t == null) return true;
        if (s == null || t == null) return false;
        if (s.val == t.val) {
            return isEqual(s.left, t.left) && isEqual(s.right, t.right);
        }
        return false;
    }

时间复杂度O(n)，空间复杂度O(1)