H1B 延期时，公司应该同时给H4办理延期吗？ - 未名空间MITBBS历史存档

H1B 延期时，公司应该同时给H4办理延期吗？# EB23 - 劳工卡

b*g2015-05-23 07:05

1 楼

Two elements of a binary search tree (BST) are swapped by mistake.
Recover the tree without changing its structure.
看了leetcode的discuss，也没给出思路。而且貌似也改变树的结构了。

l*y2015-05-23 07:05

2 楼

我H1B今年10月到期，已经发信提醒人事部renew（140 pending, 所以只能延期一年）
，但还没有收到任何答复。我的问题是H4一般应该怎样办理延期呢。我家H4没有I797
notice, 只有今年年初回国然后返美入境时的I-94和入境时护照上的印章，日期都是今
年10月。一般公司会在给h1 renew的同时给h4 办理吗（比如给h4新的I797）？请知
道的同学帮忙解答，多谢了。

c*s2015-05-23 07:05

3 楼

想象一下用O(N)空间时是咋算的，
然后将扫描数组的操作转换成inorder traversal.

【在 b****g 的大作中提到】

: Two elements of a binary search tree (BST) are swapped by mistake.
: Recover the tree without changing its structure.
: 看了leetcode的discuss，也没给出思路。而且貌似也改变树的结构了。

B*n2015-05-23 07:05

4 楼

可以一起办，但是你们公司policy如何不清楚，你问hr和律师

b*g2015-05-23 07:05

5 楼

O(N)空间难道不是首先要inorder遍历一遍吗？

【在 c***s 的大作中提到】

: 想象一下用O(N)空间时是咋算的，
: 然后将扫描数组的操作转换成inorder traversal.

c*22015-05-23 07:05

6 楼

看你们公司的policy，一般公司不帮办h4，我也没听说过有公司h1h4一起帮employee
办的。

I797

【在 l****y 的大作中提到】

: 我H1B今年10月到期，已经发信提醒人事部renew（140 pending, 所以只能延期一年）
: ，但还没有收到任何答复。我的问题是H4一般应该怎样办理延期呢。我家H4没有I797
: notice, 只有今年年初回国然后返美入境时的I-94和入境时护照上的印章，日期都是今
: 年10月。一般公司会在给h1 renew的同时给h4 办理吗（比如给h4新的I797）？请知
: 道的同学帮忙解答，多谢了。

l*a2015-05-23 07:05

7 楼

inorder traverse不用‘额外空间吗

【在 c***s 的大作中提到】

: 想象一下用O(N)空间时是咋算的，
: 然后将扫描数组的操作转换成inorder traversal.

a*r2015-05-23 07:05

8 楼

我们公司就可以H1B和H4一起办，只不过H4的申请费要自己写张Check寄给律师（公司出
律师费和H1B申请费，自己出H4的申请费）。

employee

【在 c*********2 的大作中提到】

: 看你们公司的policy，一般公司不帮办h4，我也没听说过有公司h1h4一起帮employee
: 办的。
:
: I797

c*s2015-05-23 07:05

9 楼

O(N)空间的时候就是先inorder一遍。
但按照相同的思路，并不需要在inorder的时候保存所有的节点。
所以空间可以变为O(1).
比如：用O(N)空间的时候，你的node是存在数组里，然后scan一次这个数组，
但其实你scan这个数组的操作其实跟inorder traversal的顺序是一模一样的。
所以其实你不需要用一个数组来保存nodes，而是自己用inorder traversal scan一遍
就可以了。
所需要的空间就是需要一个额外的变量来保存上一个node。

【在 b****g 的大作中提到】

: O(N)空间难道不是首先要inorder遍历一遍吗？

f*n2015-05-23 07:05

10 楼

same here

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

: 我们公司就可以H1B和H4一起办，只不过H4的申请费要自己写张Check寄给律师（公司出
: 律师费和H1B申请费，自己出H4的申请费）。
:
: employee

l*a2015-05-23 07:05

11 楼

inorder traverse不用‘额外空间吗

【在 c***s 的大作中提到】

: O(N)空间的时候就是先inorder一遍。
: 但按照相同的思路，并不需要在inorder的时候保存所有的节点。
: 所以空间可以变为O(1).
: 比如：用O(N)空间的时候，你的node是存在数组里，然后scan一次这个数组，
: 但其实你scan这个数组的操作其实跟inorder traversal的顺序是一模一样的。
: 所以其实你不需要用一个数组来保存nodes，而是自己用inorder traversal scan一遍
: 就可以了。
: 所需要的空间就是需要一个额外的变量来保存上一个node。

l*12015-05-23 07:05

12 楼

我们公司 H1 H4 给一起办，费用全部公司出。H4 EAD 费用都是公司出。

c*s2015-05-23 07:05

13 楼

你不需要记录所有nodes的话就不需要额外空间啊。
只有你要将inorder traversal的结果都记录下来时才需要O(N) 的空间。

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

: inorder traverse不用‘额外空间吗

B*n2015-05-23 07:05

14 楼

我lg公司可以，而且费用都是公司出

employee

【在 c*********2 的大作中提到】

: 看你们公司的policy，一般公司不帮办h4，我也没听说过有公司h1h4一起帮employee
: 办的。
:
: I797

l*a2015-05-23 07:05

15 楼

how do u do in-order traverse？

【在 c***s 的大作中提到】

: 你不需要记录所有nodes的话就不需要额外空间啊。
: 只有你要将inorder traversal的结果都记录下来时才需要O(N) 的空间。

A*z2015-05-23 07:05

16 楼

没听说H4不帮办的，

c*s2015-05-23 07:05

17 楼

不考虑递归函数压栈的空间，inorder traverse不需要额外空间。
如果考虑的话那就是O(logN)的空间了。
下面是我用java 写的函数。
swap[2]用来记录上一个访问的node。
swap[0]和swap[1]保存错位的nodes。
void find_node(TreeNode root, TreeNode[] swap) {
if(root == null) return;
find_node(root.left, swap);
if(swap[2] != null && swap[2].val > root.val) {
if(swap[0] == null) swap[0] = swap[2];
swap[1] = root;
}
swap[2] = root;
find_node(root.right, swap);
}

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

: how do u do in-order traverse？

l*y2015-05-23 07:05

18 楼

看来真是不同公司有不同的政策。我还在等人事部答复，确认后来更新一下。谢谢楼上
各位的信息啦。

b*g2015-05-23 07:05

19 楼

其实楼上几位反复询问的就是这个inorder怎么travel，因为如果递归的话那占用空间
肯定就不是O（1）了，用栈的话也不是O（1）。你给的的答案也用了递归，那就不是O
（1）了吧？

【在 c***s 的大作中提到】

: 不考虑递归函数压栈的空间，inorder traverse不需要额外空间。
: 如果考虑的话那就是O(logN)的空间了。
: 下面是我用java 写的函数。
: swap[2]用来记录上一个访问的node。
: swap[0]和swap[1]保存错位的nodes。
: void find_node(TreeNode root, TreeNode[] swap) {
: if(root == null) return;
: find_node(root.left, swap);
: if(swap[2] != null && swap[2].val > root.val) {
: if(swap[0] == null) swap[0] = swap[2];

m*82015-05-23 07:05

20 楼

就是

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

: 没听说H4不帮办的，

i*e2015-05-23 07:05

21 楼

Node *p, *q;
中序遍历此bst两次，第一次遍历找到一个比前驱节点小的节点记为p, 第二次遍历找
到第一个比p指向节点大的节点记为q, swap(p, q); 时间复杂度 O(n), 空间复杂度 O(
1)

l*y2015-05-23 07:05

22 楼

更新一下，公司的律师H1,H4一起办理，但H4的律师费和申请费自己出，共690刀。当年
F1转H1时，前公司没有收H4费用。

b*g2015-05-23 07:05

23 楼

Two elements of a binary search tree (BST) are swapped by mistake.
Recover the tree without changing its structure.
看了leetcode的discuss，也没给出思路。而且貌似也改变树的结构了。

c*s2015-05-23 07:05

24 楼

想象一下用O(N)空间时是咋算的，
然后将扫描数组的操作转换成inorder traversal.

【在 b****g 的大作中提到】

: Two elements of a binary search tree (BST) are swapped by mistake.
: Recover the tree without changing its structure.
: 看了leetcode的discuss，也没给出思路。而且貌似也改变树的结构了。

b*g2015-05-23 07:05

25 楼

O(N)空间难道不是首先要inorder遍历一遍吗？

【在 c***s 的大作中提到】

: 想象一下用O(N)空间时是咋算的，
: 然后将扫描数组的操作转换成inorder traversal.

l*a2015-05-23 07:05

26 楼

inorder traverse不用‘额外空间吗

【在 c***s 的大作中提到】

: 想象一下用O(N)空间时是咋算的，
: 然后将扫描数组的操作转换成inorder traversal.

c*s2015-05-23 07:05

27 楼

O(N)空间的时候就是先inorder一遍。
但按照相同的思路，并不需要在inorder的时候保存所有的节点。
所以空间可以变为O(1).
比如：用O(N)空间的时候，你的node是存在数组里，然后scan一次这个数组，
但其实你scan这个数组的操作其实跟inorder traversal的顺序是一模一样的。
所以其实你不需要用一个数组来保存nodes，而是自己用inorder traversal scan一遍
就可以了。
所需要的空间就是需要一个额外的变量来保存上一个node。

【在 b****g 的大作中提到】

: O(N)空间难道不是首先要inorder遍历一遍吗？

l*a2015-05-23 07:05

28 楼

inorder traverse不用‘额外空间吗

【在 c***s 的大作中提到】

: O(N)空间的时候就是先inorder一遍。
: 但按照相同的思路，并不需要在inorder的时候保存所有的节点。
: 所以空间可以变为O(1).
: 比如：用O(N)空间的时候，你的node是存在数组里，然后scan一次这个数组，
: 但其实你scan这个数组的操作其实跟inorder traversal的顺序是一模一样的。
: 所以其实你不需要用一个数组来保存nodes，而是自己用inorder traversal scan一遍
: 就可以了。
: 所需要的空间就是需要一个额外的变量来保存上一个node。

c*s2015-05-23 07:05

29 楼

你不需要记录所有nodes的话就不需要额外空间啊。
只有你要将inorder traversal的结果都记录下来时才需要O(N) 的空间。

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

: inorder traverse不用‘额外空间吗

l*a2015-05-23 07:05

30 楼

how do u do in-order traverse？

【在 c***s 的大作中提到】

: 你不需要记录所有nodes的话就不需要额外空间啊。
: 只有你要将inorder traversal的结果都记录下来时才需要O(N) 的空间。

c*s2015-05-23 07:05

31 楼

不考虑递归函数压栈的空间，inorder traverse不需要额外空间。
如果考虑的话那就是O(logN)的空间了。
下面是我用java 写的函数。
swap[2]用来记录上一个访问的node。
swap[0]和swap[1]保存错位的nodes。
void find_node(TreeNode root, TreeNode[] swap) {
if(root == null) return;
find_node(root.left, swap);
if(swap[2] != null && swap[2].val > root.val) {
if(swap[0] == null) swap[0] = swap[2];
swap[1] = root;
}
swap[2] = root;
find_node(root.right, swap);
}

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

: how do u do in-order traverse？

b*g2015-05-23 07:05

32 楼

其实楼上几位反复询问的就是这个inorder怎么travel，因为如果递归的话那占用空间
肯定就不是O（1）了，用栈的话也不是O（1）。你给的的答案也用了递归，那就不是O
（1）了吧？

【在 c***s 的大作中提到】

: 不考虑递归函数压栈的空间，inorder traverse不需要额外空间。
: 如果考虑的话那就是O(logN)的空间了。
: 下面是我用java 写的函数。
: swap[2]用来记录上一个访问的node。
: swap[0]和swap[1]保存错位的nodes。
: void find_node(TreeNode root, TreeNode[] swap) {
: if(root == null) return;
: find_node(root.left, swap);
: if(swap[2] != null && swap[2].val > root.val) {
: if(swap[0] == null) swap[0] = swap[2];

i*e2015-05-23 07:05

33 楼

Node *p, *q;
中序遍历此bst两次，第一次遍历找到一个比前驱节点小的节点记为p, 第二次遍历找
到第一个比p指向节点大的节点记为q, swap(p, q); 时间复杂度 O(n), 空间复杂度 O(
1)

l*i2015-05-23 07:05

34 楼

这个中序遍历怎么O（1）空间？ DFS要用到stack，循环也是啊，难道循环的不算？

O(

【在 i******e 的大作中提到】

: Node *p, *q;
: 中序遍历此bst两次，第一次遍历找到一个比前驱节点小的节点记为p, 第二次遍历找
: 到第一个比p指向节点大的节点记为q, swap(p, q); 时间复杂度 O(n), 空间复杂度 O(
: 1)

B*t2015-05-23 07:05

35 楼

贴一个, 如果递归不算extra space....
class Solution {
public:
void recoverTree(TreeNode *root, TreeNode *&pre, TreeNode *&big,
TreeNode *&small, bool &first)
{
if(root)
{
recoverTree(root->left, pre, big, small, first);
if(first && root->val < pre->val)
{
big = pre;
first = false;
}
if(root->val < pre->val)
small = root;
pre = root;
recoverTree(root->right, pre, big, small, first);
}
}
void recoverTree(TreeNode *root) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
TreeNode *pre = new TreeNode(INT_MIN);
TreeNode *big, *small;
bool first = true;
recoverTree(root, pre, big, small, first);
int temp = big->val;
big->val = small->val;
small->val = temp;
}
};

【在 b****g 的大作中提到】

: Two elements of a binary search tree (BST) are swapped by mistake.
: Recover the tree without changing its structure.
: 看了leetcode的discuss，也没给出思路。而且貌似也改变树的结构了。