今日收获：
1.如何判断一棵树 A 是不是另外一棵树 B 的子树
A== B 或者 A是B的左子树或者 A是B的右子树
那么A ==B 的条件是：A 所有节点的值和B的所有对应节点的值相等
2.树的时间复杂度要看节点的个数，假设A有 m个节点，B有n个节点
最坏情况下，每次判断A是否和B 某个节点对应的子树相同时，需要遍历A中所有的节点，所以时间复杂度为 O(m) B中所有的节点都会遍历，所以总时间复杂度 为 O(m * n)
3.树的空间复杂度要看树的深度
理论基础：递归深度，参考如下解释
Recursion depth refers to the number of recursive calls that are active at the same time. Each recursive call adds a new frame to the call stack. The depth of recursion is the maximum number of these frames that can exist simultaneously during the execution of the recursive algorithm.
所以我们有如下结论：
isSubtree Method:
The space complexity is determined by the recursion depth, which is the height of the tree.
In the worst case (skewed tree), the height is 𝑂(𝑛)
isSameTree Method:
Similarly, the space complexity is determined by the recursion depth, which is the height of the subtree being compared.
In the worst case, this height is 𝑂(𝑚)
Combined Space Complexity:
The maximum depth of recursion when both methods are called is O(n+m).
网友评论