长大后想做什么？做回小孩！

0%

LeetCode——另一个树的子树

发表于 分类于 Valine：
本文字数： 175

NO.572 另一个树的子树 简单

YZVo4K.png

YZVIN6.png

思路一：DFS 深搜将 s 的每个节点作为根节点形成一个子树，再深搜进行判断 s 的每个子树是否和 t 相等。

判断两个树相等就是 -> NO.100 相同的树 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public boolean isSubtree(TreeNode s, TreeNode t) {
    if (s == null) return false;
    //当前节点为根的子树是否相等
    if (isSame(s, t)) {
        return true;
    } else {
        //深搜
        return isSubtree(s.left, t) || isSubtree(s.right, t);
    }
}

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

时间复杂度：O(n*m) s 的节点数 n， t 的节点数 m。

空间复杂度：O(MAX(depth(s),depth(t)))

本人菜鸟，有错误请告知，感激不尽！

更多题解和源码:github