关于Binary tree recursion的空间复杂度问题

关于binary tree recursion空间复杂度，困扰我很久了。

关于时间复杂度，Recursion（包括traversal和divide&conquer）和iterative两种方法都是要遍及所有node的，所以时间复杂度总是O(n); （这里的N是node总数）
而空间复杂度，一般是height of tree，那么平均角度来说就是log(N),因为在完成children level程序之前，所有的parent level都是在运行的。

但是，一般recusion-divide&conquer使用的是系统stack的空间，
而如果我们如果做traversal需要建立new ArrayList用的是heap空间；
同样iterative way建立new Stack也用的是heap空间
而我看九章算法，说，大部分面试官认为的“空间复杂度”专门指的是heap，不包括stack，这个你要和面试官扯清楚。。。如下：
https://www.jiuzhang.com/qa/425/

反正我已经晕了。。。不知道我上面说的是否正确，然后大家如何看待这个问题呢？面试会考这个么？

举个例子
https://leetcode.com/problems/po ... h-node/description/
116题，要求no extra constant space

我的代码是：
public void connect(TreeLinkNode root) {
      if (root == null) return;
      if (root.left != null) {
          root.left.next = root.right;
          if (root.next != null) {
              root.right.next = root.next.left;
          }
      }
      connect(root.left);
      connect(root.right);
    }


我的这段code，纯recursion，没有new任何的ArrayList啥的，所以：
1. 如果stack+heap都算上的话，应该是占用了stack空间O(height),
2.如果只算heap的话，占用空间是O(1)?

诚心请教，非常感谢大家！

这个我觉得你可能是误解了九章的意思，你给的链接里的原话是“一般堆和栈都要计算在内，但是有的时候面试官想表达的是栈空间不算，只算堆空间。所以在这一点上，你要和 面试官扯皮扯清楚”。注意他说的是“有的面试官”，并非“大部分面试官”。确实一般说额外空间要包括任何使用的内存，无论是堆和栈。但是，你也不能保证所有的面试官都这样认为，或者面试官故意表达得很含糊，看你是否能区分这两者，所以在不确定的情况下扯清楚确实是最好的选择。

所以具体到Leetcode 116, no extra constant space确实可以有两种理解。如果面试官的意思是2，那这个答案就是可以的；但是如果面试官的意思是1，那这个答案就是不合格的。所以这种情况下真的要提前交流清楚。

CC189上第一章有讲解，stack的是临时的到下一层recursion就被回收了，所以stack的几乎可以忽略不计。

recursion的复杂度当然是O(h),这个没有争议。九章的意思就是有的面试官自己算法没学明白，误以为recursion是O(1)，你可以clarify一下，别因为面试官自己的水平问题耽误你的答题。用recursion和用stack这个是可以等价互换的，如果recursion空间是O(1)，那stack就是O(1)空间复杂度的数据结构了，这太荒谬了。

stellari 发表于 2017-9-1 02:42
这个我觉得你可能是误解了九章的意思，你给的链接里的原话是“一般堆和栈都要计算在内，但是有的时候面试官 ...

非常感谢！
我还有一个followup问题，也很白痴的问题

到底什么是空间复杂度？是完成整个过程所需的space，还是“临时”需要的呢？

我前面的divide&conquer的例子，每一层recursion，都是要消耗一份stack，所以是O(height)，这里显然时间复杂度指的是“临时”

那如果我是用recursion来tree traversal，我们在heap里开辟一个ArrayList来存储node，同时return void，那么：
1. 因为recursion的关系，所以stack还是要消耗O(height)?
2. 那么heap的空间复杂度是多少呢？如果指的是我要存储所有的node，那么就是O(n); 如果是“临时”，还是O（height）？

不知道我表达清楚了没有。

biomedicineman 发表于 2017-9-1 12:58
非常感谢！
我还有一个followup问题，也很白痴的问题

要正确回答空间复杂度，只需要关心一件事：在这个算法需要占用内存最多的那一时刻，内存使用量是多少？所以，假如说你在heap中把n个node都复制了一份，而又没有删除过其中任何一个。那也就是说在某一时刻肯定至少需要O(n)内存。再加上recursion可能需要的内存O(height)，那么总时间复杂度还是O(n + height) = O(n)。

顺带一提，刷题界谈的空间复杂度一般是不包括input所占内存的。具体到这道题，那就是说假如在调用connect前，这棵树就已经存在了的话，那么这棵树的原node所占空间不计入考虑范围。但是如果你自己clone了其中的某些node，这些clone的占用空间需要考虑。

举个例子你可能比较好理解了，这个程序就相当于一个游乐园，空间复杂度不是这个游乐园今天一共来了多少人，而是在人最多时游乐园里有多少人

castielsunny 发表于 2017-9-4 15:49
举个例子你可能比较好理解了，这个程序就相当于一个游乐园，空间复杂度不是这个游乐园今天一共来了多少人， ...

对对。我懂。
那么followup问题是，游乐园里"最多"有多少人，是否要包括both heap and stack?

我觉得你其实理解的挺清楚的了. 大部分的题目的空间要求确实单指heap, 但是也有些题目是连Stack也要算上的, 因为有些要求O(1)空间的题目有些人会想要把循环写成recursion来规避空间要求. recursion stack到底算不算在题目限制以内, 这个你面试的时候实际问一下面试官就行了, 其实这个问题LeetCode上也没少被人扯皮过.