same tree那道题如果用递归做，空间复杂度是多少？

有的说是o(1),有的说是o(logn)，到第是哪个？谢谢

public boolean isSameTree(TreeNode p, TreeNode q) {  
    if(p==null && q==null)  
        return true;  
    if(p==null || q==null)  
        return false;  
    if(p.val!=q.val)  
        return false;  
    return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);  
}

准确说是O(p和q两者中较浅的tree的深度)。在p和q都是平衡树的情况下，这一深度等于logN。

每次进入下一层递归时，都会在栈上新创建一对p和q，这是一个常数量级的内存消耗。所以，整个算法需要的最大空间就是（可能的最大递归深度 * 常数）。

说空间复杂度是O(1)的是没有考虑栈内存的使用情况，但个人认为这是不合理的。从理论角度而言，内存的使用量与内存的种类和分配方式无关；从实际角度而言，可用的栈空间一般情况下都很小（megabyte量级），递归深度较深时很容易导致stack overflow，这是不能不考虑的一个现实情况。

stellari 发表于 2017-12-31 10:52
准确说是O(p和q两者中较浅的tree的深度)。在p和q都是平衡树的情况下，这一深度等于logN。

每次进入下一 ...

请问时间复杂度呢？

cheese_harry 发表于 2017-12-31 11:11
请问时间复杂度呢？

设p和q都是平衡树，且节点数都是N的话，那么函数的执行时间是T(N) = 2T(N/2) + K，满足这个递推条件的复杂度是O(N)。

stellari 发表于 2017-12-31 18:05
设p和q都是平衡树，且节点数都是N的话，那么函数的执行时间是T(N) = 2T(N/2) + K，满足这个递推条件的复 ...

层主，如果是满足T(N) = A x T(N) + K, A是一个常数，比如3，4，那么整体是O(N) 的复杂度吗？ 谢谢啦

blackie 发表于 2018-1-8 15:19
层主，如果是满足T(N) = A x T(N) + K, A是一个常数，比如3，4，那么整体是O(N) 的复杂度吗？ 谢谢啦

写错了，应该是，T(N) = A x T(N/A) + K, A是一个常数

worst case o(n), n node的数量

best case o(1), 第一个不等就返回了

我觉得时间是O(n),空间是O(1). 虽然是recursion，不过是为tail recursion. frame在stack中创建后直接弹出了。欢迎交流。

时间O[n] 显然, 最坏情况要检查每个node

空间应该是O[lgn], 因为你坚持也只会一次一条线的走到底, 这个高度是lgn, 是stack space.

按理来说你认为是o[1]的理由是没有new过任何地址, 这样说也不能算错.