关于485提交的这个时间问题 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>EB23 - 劳工卡

关于485提交的这个时间问题

关于485提交的这个时间问题# EB23 - 劳工卡

g*j2018-03-02 08:03

1 楼

要求不用额外空间，O(n)时间。

m*d2018-03-02 08:03

2 楼

看有几个面试被拒的朋友都提到了是filing date和final date的问题
有点confuse，一排current了就可以提交485这个没有什么问题吧
现在3月的一排是11月15日2014
我的PD是10/17/2014，应该可以提交了吧

r*g2018-03-02 08:03

3 楼

两个树node一起走一起比较啊，难道有特殊的要求

S*u2018-03-02 08:03

4 楼

可以提交，没有问题

a*r2018-03-02 08:03

5 楼

我的算法：
对两个BST同时进行in-order traversal in an iterative way.
bool is_BST_eq(TreeNode *r1, TreeNode *r2){
if(r1 == nullptr && r2 == nullptr) return true;

stack st1;
stack st2;

TreeNode *p = r1;
TreeNode *n1 = nullptr;
TreeNode *q = r2;
TreeNode *n2 = nullptr;

while(true){

// iterative inorder traversal for r1
while(!st1.empty() || p){
if(p){
st1.push(p);
p = p->left;
}else{
p = st1.top();
st1.pop();
n1 = p;
p = p->right;
break;
}
}

// iterative inorder traversal for r2
while(!st2.empty() || q){
if(q){
st2.push(q);
q = q->left;
}else{
q = st1.top();
st2.pop();
n2 = q;
q = q->right;
break;
}
}

// n1 and n2 should not be null.
if(n1->val != n2->val) return false;
else{
if(st1.empty() && st2.empty()) return true;
else if(!st1.empty() && st2.empty()) return false;
else if(st1.empty() && !st2.empty()) retufn false;
else continue;
}
}
}

z*a2018-03-02 08:03

6 楼

Lz确定这题对的？不说比较两棵树，有O(1)空间，O(n)时间遍历二叉树的算法么？

z*a2018-03-02 08:03

7 楼

你这空间复杂度明显是O(lgn)吧

【在 a****r 的大作中提到】

: 我的算法：
: 对两个BST同时进行in-order traversal in an iterative way.
: bool is_BST_eq(TreeNode *r1, TreeNode *r2){
: if(r1 == nullptr && r2 == nullptr) return true;
:
: stack st1;
: stack st2;
:
: TreeNode *p = r1;
: TreeNode *n1 = nullptr;

a*r2018-03-02 08:03

8 楼

空间复杂度O(n). 最好是O(lgn)。constant space 应该不太可能解这道题吧？牛人可
以指点一下。

【在 z**a 的大作中提到】

: 你这空间复杂度明显是O(lgn)吧