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);
    }
}

复杂度分析

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

解法二

思路

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

代码

复杂度分析

时间复杂度

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

Takeaway

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