请问这道题我的接发的时间复杂度是？

刷题一直都没在意Time complexity和Space complexity。。。惭愧。最近开始练习分析大O，但这道题实在不会了，请问它的时间复杂度是，以及如何分析？谢谢啦！！

1. /**
   
2. * Definition for a binary tree node.
   
3. * public class TreeNode {
   
4. *     int val;
   
5. *     TreeNode left;
   
6. *     TreeNode right;
   
7. *     TreeNode(int x) { val = x; }
   
8. * }
   
9. */
   
10. class Solution {
    
11.    
    
12.     // The list stores all the possible nodes whose values are the same as t's value
    
13.     ArrayList<TreeNode> list = new ArrayList<>();
    
14.     int target;
    
15.    
    
16.     public boolean isSubtree(TreeNode s, TreeNode t) {
    
17.         
    
18.         target = t.val;
    
19.         
    
20.         // Depth first search s, find all the possible nodes
    
21.         dfs(s);
    
22.         
    
23.         if(list.isEmpty())
    
24.             return false;
    
25.         
    
26.         for(TreeNode node : list){
    
27.             if(isIdentical(node, t))
    
28.                 return true;
    
29.         }
    
30.         
    
31.         return false;   
    
32.     }
    
33.    
    
34.    
    
35.     public void dfs(TreeNode s){
    
36.         if(s == null)
    
37.             return;
    
38.         if(s.val == target)
    
39.             list.add(s);
    
40.         dfs(s.left);
    
41.         dfs(s.right);
    
42.     }
    
43.    
    
44.     public boolean isIdentical(TreeNode s, TreeNode t){
    
45.         
    
46.                 // The s and t should reach the end of the trees together
    
47.         if(s == null && t == null)
    
48.             return true;
    
49.         if(s == null || t == null)
    
50.             return false;
    
51.         if(s.val != t.val)
    
52.             return false;
    
53.             
    
54.         return isIdentical(s.left, t.left) && isIdentical(s.right, t.right);
    
55.     }
    
56. }

复制代码

设 |X| = 以 X 为树根的subtree中的节点总数

那么：

isIdentical(TreeNode s, TreeNode t)的时间复杂度 = O( min(|s|, |t|) )

dfs(TreeNode s)的时间复杂度 = O(|s|)

isSubtree(TreeNode s, TreeNode t)的时间复杂度 = dfs(TreeNode s)的时间复杂度 + |s| * isIdentical(TreeNode s, TreeNode t)的时间复杂度 = O( |s| * min(|s|, |t|) ) <= O( |s| * |t| )

忘记说：isSubtree(TreeNode s, TreeNode t)是主方法。题目：https://leetcode.com/problems/subtree-of-another-tree/

magicsets 发表于 2019-10-11 11:27
设 |X| = 以 X 为树根的subtree中的节点总数

那么：

太感谢了！！