g***j
发帖数: 1275 | |
r*********g
发帖数: 67 | 2 两个树node一起走一起比较啊，难道有特殊的要求 |
a****r
发帖数: 87 | 3 我的算法：
对两个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**a
发帖数: 69 | 4 Lz确定这题对的？不说比较两棵树，有O(1)空间，O(n)时间遍历二叉树的算法么？ |
z**a
发帖数: 69 | 5 你这空间复杂度明显是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****r
发帖数: 87 | 6 空间复杂度O(n). 最好是O(lgn)。constant space 应该不太可能解这道题吧？牛人可
以指点一下。
【在 z**a 的大作中提到】
: 你这空间复杂度明显是O(lgn)吧
|
t**********h
发帖数: 2273 | 7 morris搞起？
【在 g***j 的大作中提到】
: 要求不用额外空间，O(n)时间。
|
q*****o
发帖数: 40 | |
l*****4
发帖数: 267 | |
