谁给分析一下为什么树的前序遍历，空间复杂度是lgN?

自己数学不好这太吃亏了。对于分析时空复杂度的，有些能看懂，有些根本就是凭感觉。
比如这个，树的前序遍历，空间复杂度是lgN，是怎么分析出来的。
感谢大家的帮助。

这个和数学没有关系，和具体的算法有关系。
能不能把具体算法描述一下呢？

我的理解如果只是打印一下，根本不需要什么空间复杂度啊。。。。

如果是循环实现，那么需要开一个栈，在平衡二叉树的条件下，空间复杂度是O(log2(n))
如果是递归实现，空间复杂度是O(1)

robinho364 发表于 2015-9-20 19:46
这个和数学没有关系，和具体的算法有关系。
能不能把具体算法描述一下呢？

你错了，递归方法是需要栈空间的。仍为O(lgN)。

robinho364 发表于 2015-9-20 19:46
这个和数学没有关系，和具体的算法有关系。
能不能把具体算法描述一下呢？

1. /**
   
2. * Definition for a binary tree node.
   
3. * struct TreeNode {
   
4. *     int val;
   
5. *     TreeNode *left;
   
6. *     TreeNode *right;
   
7. *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
   
8. * };
   
9. */
   
10. class Solution {
    
11. public:
    
12.     bool isSameTree(TreeNode* p, TreeNode* q) {
    
13. 
    
14.         stack<TreeNode*> myStack;
    
15.         myStack.push(p);
    
16.         myStack.push(q);
    
17.       
    
18.         while(!myStack.empty())
    
19.         {
    
20.             p = myStack.top();
    
21.             myStack.pop();
    
22.             q = myStack.top();
    
23.             myStack.pop();
    
24.             if(canSuccess(p,q))
    
25.             {
    
26.                 if(!p && !q)
    
27.                     continue;
    
28.                 if(p->val != q->val)
    
29.                     return false;
    
30.                 //采用先序遍历法 NLR   
    
31.                 myStack.push(p->right);
    
32.                 myStack.push(q->right);
    
33.                 myStack.push(p->left);
    
34.                 myStack.push(q->left);
    
35.             }else{
    
36.                 return false;
    
37.             }
    
38.         }
    
39.         return true;
    
40.     }
    
41.    
    
42.     bool canSuccess(TreeNode* p, TreeNode*q){
    
43.         if(!p && !q)
    
44.             return true;
    
45.         else if(p && !q)
    
46.             return false;
    
47.         else if(!p && q)
    
48.             return false;
    
49.         else if(p->val != q->val)
    
50.             return false;
    
51.         
    
52.         return true;
    
53.     }
    
54. };

复制代码

你这里的lgN应该指的二叉树遍历的空间复杂度。空间复杂度记得是程序额外需占用的空间大小的度量，二叉树本身节点存储需要O(N)空间复杂度，二叉树前序遍历时需要额外的O(lgN)空间复杂度，用于栈空间。lgN是树高。

robinho364 发表于 2015-9-20 19:46
这个和数学没有关系，和具体的算法有关系。
能不能把具体算法描述一下呢？

递归只是不是自己显式地写出栈，程序运行的时候要保存上一次递归结果是要压入内存的栈的

robinho364 发表于 2015-9-20 19:46
这个和数学没有关系，和具体的算法有关系。
能不能把具体算法描述一下呢？

这和具体的算法（除了Morris Traversal）还真没啥关系，无论迭代还是递归，都要至少用到O(logN)额外内存。不能因为我们看不到后者中栈空间的消耗情况，就说这时不存在内存消耗啊。

stellari 发表于 2015-9-20 22:51
这和具体的算法（除了Morris Traversal）还真没啥关系，无论迭代还是递归，都要至少用到O(logN)额外内存 ...

反对以上意见，所谓的程序内部的栈，和算法的栈没有关系。

robinho364 发表于 2015-9-20 23:10
反对以上意见，所谓的程序内部的栈，和算法的栈没有关系。

反对我自己的回答，根据wiki的解释：

https://en.wikipedia.org/wiki/DSPACE

It represents the total amount of memory space that a "normal" physical computer would need to solve a given computational problem with a given algorithm.

此外：

http://www.geeksforgeeks.org/g-fact-86/

zjuzqh 发表于 2015-9-20 20:04
你错了，递归方法是需要栈空间的。仍为O(lgN)。

我错了