572. Subtree of Another Tree

解法一#

思路#

分解成两个问题。
一是什么是判断是否 subtree 的条件？
如果 s 不为 null， 判断一个树是否是另一个树的 subtree，有三种情况满足其中一种就行：

1. TreeNode s 和 TreeNode t 代表的树相等；
2. TreeNode s 的左子树和 TreeNode t 的树相等；
3. TreeNode s 的右子树和 TreeNode t 的树相等；
   如果 s 为 null，那么是否 subtree 取决于 t 是否为 null。
   二是判断两树相等的条件？
   这个曾经出现在 100 题 Same Tree 中。

代码#

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

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

复杂度分析#

• 时间复杂度
  • 最好情况 两树相等，O (n) 复杂度 - equals () 方法遍历每个节点。
  • 最坏情况 遍历 s 树的所有节点，检查每个子树是否和 t 相等。 O (m * n)
  • 平均情况 O (m * n)
• 空间复杂度
  • 最坏情况 O (m), 储存 s 树所有元素
  • 最好情况 O (logm), 平衡二叉树

解法二#

思路#

尝试用 iteration 的方法来写 isSubtree ()

代码#

复杂度分析#

时间复杂度

• 最好情况
• 最坏情况
• 平均情况
  空间复杂度

Takeaway#

本作品采用《CC 协议》，转载必须注明作者和本文链接