Convert Binary Search Tree to Sorted Doubly Linked List 这题怎么分析时间复杂度

题目：
https://leetcode.com/explore/interview/card/facebook/52/trees-and-graphs/544/

其中一个解法是先建立一个helper function用来吧两个doubly linked list衔接起来，然后递归地把整个tree的每个node的left/right都改了，解法：
https://www.geeksforgeeks.org/convert-a-binary-tree-to-a-circular-doubly-link-list/

但这个解法的空间复杂度是多少？这种递归法怎么去分析空间复杂度？

空间复杂度是O(h)，h是树的高度。

首先转换过程中没有"new"，也就是没有创建堆区对象。

所以空间使用都是在栈区 —— 这里有个知识点是递归过程中每往下调用一层是要创建Stack Frame的。而且对于链接里那个实现来说，在往下调用时，除去一些固有的overhead（frame pointer之类的，某些面试官可能会说这不算在耗用空间里），当前栈上至少需要保存参数root和局部变量left，这两个应当算作是算法所消耗的空间。

此外，"concatenate"的调用不在递归链上，且使用常数栈区空间，可以忽略。

所以空间使用是和栈的最大层数（递归的最大深度）成正比的，也就是O(h)。

谢谢！ 其实我更感兴趣的是时间复杂度，这道题怎么分析时间复杂度？

ProInterviewer 发表于 2018-5-5 13:18
谢谢！ 其实我更感兴趣的是时间复杂度，这道题怎么分析时间复杂度？

时间复杂度是O(n)，n是tree中的node总数

在bTreeToCList()中，除去递归部分，余下的运算（主要是两次concatenate调用）是常数时间。

所以时间复杂度正比于bTreeToCList()被调用的次数，也就是(1) tree中node总数 + (2) null叶子节点总数。

其中(1)的数量为n，在处理(1)时是要调用两次concatenate的；而(2)的数量为n+1，在处理(2)时在if (root == NULL)那里就返回了 —— 当然我们其实不用考虑这些细节，直接O(n + (n + 1)) = O(n)就行。

1. class Solution {
   
2.     public Node treeToDoublyList(Node root) {
   
3.         if(root == null) return null;
   
4.         id(root);
   
5.         // now p is at last node, c is still root
   
6.         c.right.left = p;
   
7.         p.right = c.right;
   
8.         return c.right;
   
9.     }
   
10.    
    
11.     Node p = new Node(0, null, null), c = p;
    
12.    
    
13.     void id(Node r)
    
14.     {
    
15.         if(r == null) return;
    
16.         id(r.left);
    
17.         // now visit root
    
18.         p.right = r;
    
19.         r.left = p;
    
20.         p = p.right;
    
21.         id(r.right);
    
22.     }
    
23. }

复制代码

和114差不多一个意思， in order traversal, 然后连接节点。用一个外部节点来代表头，可以串起来。
时间复杂当然是O(n)， 把树的每个节点都走了一遍。
空间复杂是O(log n), 也就是高度。 因为是bst所以是lg n。 因为会一直调用函数直到最底下那个点。