EB1B请教# Immigration - 落地生根
l*y
1 楼
Given a binary tree, find the minimum sum from root to the leaf and also print that path?
C*y
2 楼
1，能用自己的check支付I-140吗？
2，8papers，300引用，claim了pub和contribution。纠结要不要pp？
2，8papers，300引用，claim了pub和contribution。纠结要不要pp？
S*w
3 楼
dp?
the
【在 l*********y 的大作中提到】
: Given a binary tree, find the minimum sum from root to the leaf and also print that path?
the
【在 l*********y 的大作中提到】
: Given a binary tree, find the minimum sum from root to the leaf and also print that path?
T*y
4 楼
yes.
why not? well, nobody can ensure you the result.
【在 C*********y 的大作中提到】
: 1，能用自己的check支付I-140吗？
: 2，8papers，300引用，claim了pub和contribution。纠结要不要pp？
a*m
5 楼
dij吧。
C*y
6 楼
thanks. baozi sent
a*m
7 楼
感觉dp似乎木有啥帮助。本来也是要遍历。
【在 S*******w 的大作中提到】
: dp?
:
: the
【在 S*******w 的大作中提到】
: dp?
:
: the
T*y
8 楼
wow, thanks a lot! I didn't expect it.
Best wishes to you! May it pass like a breeze!
【在 C*********y 的大作中提到】
: thanks. baozi sent
Best wishes to you! May it pass like a breeze!
【在 C*********y 的大作中提到】
: thanks. baozi sent
S*w
9 楼
shortest path algorithm都行啊
【在 S*******w 的大作中提到】
: dp?
:
: the
【在 S*******w 的大作中提到】
: dp?
:
: the
w*r
10 楼
Yes，we used our own check.
【在 C*********y 的大作中提到】
: 1，能用自己的check支付I-140吗？
: 2，8papers，300引用，claim了pub和contribution。纠结要不要pp？
【在 C*********y 的大作中提到】
: 1，能用自己的check支付I-140吗？
: 2，8papers，300引用，claim了pub和contribution。纠结要不要pp？
S*w
11 楼
dp可以解。
【在 a********m 的大作中提到】
: 感觉dp似乎木有啥帮助。本来也是要遍历。
【在 a********m 的大作中提到】
: 感觉dp似乎木有啥帮助。本来也是要遍历。
s*n
12 楼
Strong enough for EB1b, you can try PP.
【在 C*********y 的大作中提到】
: 1，能用自己的check支付I-140吗？
: 2，8papers，300引用，claim了pub和contribution。纠结要不要pp？
【在 C*********y 的大作中提到】
: 1，能用自己的check支付I-140吗？
: 2，8papers，300引用，claim了pub和contribution。纠结要不要pp？
q*x
13 楼
有帮助。省下重复计算。
【在 a********m 的大作中提到】
: 感觉dp似乎木有啥帮助。本来也是要遍历。
【在 a********m 的大作中提到】
: 感觉dp似乎木有啥帮助。本来也是要遍历。
s*t
14 楼
Strong enough for EB1b, try pp
a*m
15 楼
不管是遍历还是dij所有新节点的值都是没有计算过的。没有重复计算吧。
【在 q****x 的大作中提到】
: 有帮助。省下重复计算。
【在 q****x 的大作中提到】
: 有帮助。省下重复计算。
C*y
16 楼
thanks guys. bao zi
l*y
17 楼
难点在如何打印最短路径。dp的话得先遍历一遍才能得到有多少个节点吧。
l*y
18 楼
Dij的话不是weight在边上,这个是weight在节点上。
a*m
19 楼
这个无所谓。你可以把节点上的值当成it到父节点的路径weight。root的反正要加在所
有路径上，没关系了。
【在 l*********y 的大作中提到】
: Dij的话不是weight在边上,这个是weight在节点上。
有路径上，没关系了。
【在 l*********y 的大作中提到】
: Dij的话不是weight在边上,这个是weight在节点上。
q*x
20 楼
那不就是dp。
【在 a********m 的大作中提到】
: 不管是遍历还是dij所有新节点的值都是没有计算过的。没有重复计算吧。
【在 a********m 的大作中提到】
: 不管是遍历还是dij所有新节点的值都是没有计算过的。没有重复计算吧。
D*g
21 楼
如果可以自定义tree node structure应该很容易，每个节点上加一个sumFromRoot和
parent指针就可以了。
print that path?
【在 l*********y 的大作中提到】
: Given a binary tree, find the minimum sum from root to the leaf and also print that path?
parent指针就可以了。
print that path?
【在 l*********y 的大作中提到】
: Given a binary tree, find the minimum sum from root to the leaf and also print that path?
a*m
22 楼
。。。。。。dp本质是避免重复计算呀。。。。木有重复计算咋算dp? 这个是俺自己的
理解， 哪个大牛来说一说？
【在 q****x 的大作中提到】
: 那不就是dp。
理解， 哪个大牛来说一说？
【在 q****x 的大作中提到】
: 那不就是dp。
q*x
23 楼
通过记录之前的结果避免重复计算。
【在 a********m 的大作中提到】
: 。。。。。。dp本质是避免重复计算呀。。。。木有重复计算咋算dp? 这个是俺自己的
: 理解， 哪个大牛来说一说？
【在 a********m 的大作中提到】
: 。。。。。。dp本质是避免重复计算呀。。。。木有重复计算咋算dp? 这个是俺自己的
: 理解， 哪个大牛来说一说？
y*u
24 楼
这题和dp有什么关系啊
就是dfs，每次找到的路径sum可以作为约束，用来剪枝
站: BBS 未名空间站 (Sun Jan 1 22:36:30 2012, 美东)
【在 S*******w 的大作中提到】
: dp可以解。
就是dfs，每次找到的路径sum可以作为约束，用来剪枝
站: BBS 未名空间站 (Sun Jan 1 22:36:30 2012, 美东)
【在 S*******w 的大作中提到】
: dp可以解。
y*u
25 楼
不需要
维护2个stack，每次Pop的时候，第一个stack得到访问的节点，第二个stack是根到该
节点的sum
【在 a********m 的大作中提到】
: 。。。。。。dp本质是避免重复计算呀。。。。木有重复计算咋算dp? 这个是俺自己的
: 理解， 哪个大牛来说一说？
维护2个stack，每次Pop的时候，第一个stack得到访问的节点，第二个stack是根到该
节点的sum
【在 a********m 的大作中提到】
: 。。。。。。dp本质是避免重复计算呀。。。。木有重复计算咋算dp? 这个是俺自己的
: 理解， 哪个大牛来说一说？
H*e
26 楼
这题跟dp啥关系啊？
也用不着dijkstra,就是简单的pre-order traversal就可以勒。
inside a class:
private List minPath = new ArrayList();
private int minSum = Integer.MAX_VALUE;
private void minSumPathFromRootToLeave(BSTNode node,
ArrayList path, int currentSum) {
//path is the path from root to node's parent,
//currentSum is sum from root till node's parent
// add base cases here:
if(node == null){
return;
}
currentSum = currentSum + node.key;
path.add(node);
if (node.left == null && node.right == null) {
if (currentSum < minSum) {
minSum = currentSum;
minPath.clear();
minPath.addAll(path);
}
return;
}
minSumPathFromRootToLeave(node.left, path, currentSum);
minSumPathFromRootToLeave(node.right, path, currentSum);
path.remove(node);
}
public void printMinSumPathFromRootToLeave() {
ArrayList path = new ArrayList();
int currentSum = 0;
minSumPathFromRootToLeave(root, path, currentSum);
for (BSTNode node : minPath) {
System.out.print(node.key + " ");
}
}
也用不着dijkstra,就是简单的pre-order traversal就可以勒。
inside a class:
private List
private int minSum = Integer.MAX_VALUE;
private void minSumPathFromRootToLeave(BSTNode node,
ArrayList
//path is the path from root to node's parent,
//currentSum is sum from root till node's parent
// add base cases here:
if(node == null){
return;
}
currentSum = currentSum + node.key;
path.add(node);
if (node.left == null && node.right == null) {
if (currentSum < minSum) {
minSum = currentSum;
minPath.clear();
minPath.addAll(path);
}
return;
}
minSumPathFromRootToLeave(node.left, path, currentSum);
minSumPathFromRootToLeave(node.right, path, currentSum);
path.remove(node);
}
public void printMinSumPathFromRootToLeave() {
ArrayList
int currentSum = 0;
minSumPathFromRootToLeave(root, path, currentSum);
for (BSTNode node : minPath) {
System.out.print(node.key + " ");
}
}
a*m
27 楼
恩。dij还要排序，不值得。直接遍历就好了。
【在 H***e 的大作中提到】
: 这题跟dp啥关系啊？
: 也用不着dijkstra,就是简单的pre-order traversal就可以勒。
: inside a class:
: private List minPath = new ArrayList();
: private int minSum = Integer.MAX_VALUE;
: private void minSumPathFromRootToLeave(BSTNode node,
: ArrayList path, int currentSum) {
: //path is the path from root to node's parent,
: //currentSum is sum from root till node's parent
: // add base cases here:
【在 H***e 的大作中提到】
: 这题跟dp啥关系啊？
: 也用不着dijkstra,就是简单的pre-order traversal就可以勒。
: inside a class:
: private List
: private int minSum = Integer.MAX_VALUE;
: private void minSumPathFromRootToLeave(BSTNode node,
: ArrayList
: //path is the path from root to node's parent,
: //currentSum is sum from root till node's parent
: // add base cases here:
p*2
28 楼
我写了个C#的，发现在纸上写好，到了VS上还是要改很多。
static void minSum(Node root)
{
if (root == null)
return;
List list = new List();
List minlist = new List();
list.Add(root);
Check(list, ref minlist);
Console.WriteLine(minlist.Count-1);
foreach (Node i in minlist)
i.Print();
}
static void Check(List list, ref List minlist)
{
Node node = list[list.Count - 1];
if (node.left == null && node.right==null)
{
if (minlist.Count==0 || minlist.Count>list.Count)
{
minlist.Clear();
minlist.AddRange(list);
}
}
else
{
if (node.left != null)
{
list.Add(node.left);
Check(list, ref minlist);
}
if (node.right != null)
{
list.Add(node.right);
Check(list, ref minlist);
}
}
list.RemoveAt(list.Count - 1);
}
static void minSum(Node root)
{
if (root == null)
return;
List
List
list.Add(root);
Check(list, ref minlist);
Console.WriteLine(minlist.Count-1);
foreach (Node i in minlist)
i.Print();
}
static void Check(List
{
Node node = list[list.Count - 1];
if (node.left == null && node.right==null)
{
if (minlist.Count==0 || minlist.Count>list.Count)
{
minlist.Clear();
minlist.AddRange(list);
}
}
else
{
if (node.left != null)
{
list.Add(node.left);
Check(list, ref minlist);
}
if (node.right != null)
{
list.Add(node.right);
Check(list, ref minlist);
}
}
list.RemoveAt(list.Count - 1);
}
f*l
29 楼
C++ version
class Node
{
public:
Node() {
leftChild = NULL ;
rightChild = NULL ;
}
~Node() {}
int value ;
Node *leftChild ;
Node *rightChild ;
};
// pre-order traverse
void traverseTree(Node *treeNode, vector &path , vector
{
if ( treeNode!=NULL )
{
currentSum += treeNode->value ;
}
else
{
if( currentSum < minSum )
{
minSum = currentSum ;
miniPath.clear() ;
for (int i = 0 ; i < path.size() ; i++)
{
miniPath.push_back( path[i] );
}
}
return ;
}
if ( currentSum > minSum )
{
return ;
}
path.push_back(treeNode) ;
traverseTree(treeNode->leftChild, path, miniPath, minSum, currentSum) ;
traverseTree(treeNode->rightChild, path, miniPath, minSum, currentSum) ;
path.pop_back();
currentSum -= treeNode->value ;
return ;
}
【在 p*****2 的大作中提到】
: 我写了个C#的，发现在纸上写好，到了VS上还是要改很多。
: static void minSum(Node root)
: {
: if (root == null)
: return;
: List list = new List();
: List minlist = new List();
: list.Add(root);
: Check(list, ref minlist);
: Console.WriteLine(minlist.Count-1);
class Node
{
public:
Node() {
leftChild = NULL ;
rightChild = NULL ;
}
~Node() {}
int value ;
Node *leftChild ;
Node *rightChild ;
};
// pre-order traverse
void traverseTree(Node *treeNode, vector
{
if ( treeNode!=NULL )
{
currentSum += treeNode->value ;
}
else
{
if( currentSum < minSum )
{
minSum = currentSum ;
miniPath.clear() ;
for (int i = 0 ; i < path.size() ; i++)
{
miniPath.push_back( path[i] );
}
}
return ;
}
if ( currentSum > minSum )
{
return ;
}
path.push_back(treeNode) ;
traverseTree(treeNode->leftChild, path, miniPath, minSum, currentSum) ;
traverseTree(treeNode->rightChild, path, miniPath, minSum, currentSum) ;
path.pop_back();
currentSum -= treeNode->value ;
return ;
}
【在 p*****2 的大作中提到】
: 我写了个C#的，发现在纸上写好，到了VS上还是要改很多。
: static void minSum(Node root)
: {
: if (root == null)
: return;
: List
: List
: list.Add(root);
: Check(list, ref minlist);
: Console.WriteLine(minlist.Count-1);
m*n
30 楼
public int miniSum(Node tree) {
if(tree==null) return 0;
if(tree!=null && tree.left ==null && tree.right==null) return tree.
value;
int left= miniSum(tree.left);
int right = miniSum(tree.right);
return Math.min(left,right)+tree.value;
}
if(tree==null) return 0;
if(tree!=null && tree.left ==null && tree.right==null) return tree.
value;
int left= miniSum(tree.left);
int right = miniSum(tree.right);
return Math.min(left,right)+tree.value;
}
m*n
31 楼
带返回路径的
public int miniSum(Node tree, ArrayList pre) {
if(tree==null) return 0;
if(tree!=null && tree.left ==null && tree.right==null) {
pre.add(tree);
return tree.value;
}
ArrayList storeresult = new ArrayList();
int left= miniSum(tree.left, storeresult);
ArrayList storeresultright = new ArrayList();
int right = miniSum(tree.right,storeresultright);
pre.add(tree);
if(left
}
else{
pre.addAll(storeresultright);
}
return Math.min(left,right)+tree.value;
}
public int miniSum(Node tree, ArrayList
if(tree==null) return 0;
if(tree!=null && tree.left ==null && tree.right==null) {
pre.add(tree);
return tree.value;
}
ArrayList
int left= miniSum(tree.left, storeresult);
ArrayList
int right = miniSum(tree.right,storeresultright);
pre.add(tree);
if(left
}
else{
pre.addAll(storeresultright);
}
return Math.min(left,right)+tree.value;
}
h*w
32 楼
mark一下，顺便support这个解法
【在 H***e 的大作中提到】
: 这题跟dp啥关系啊？
: 也用不着dijkstra,就是简单的pre-order traversal就可以勒。
: inside a class:
: private List minPath = new ArrayList();
: private int minSum = Integer.MAX_VALUE;
: private void minSumPathFromRootToLeave(BSTNode node,
: ArrayList path, int currentSum) {
: //path is the path from root to node's parent,
: //currentSum is sum from root till node's parent
: // add base cases here:
【在 H***e 的大作中提到】
: 这题跟dp啥关系啊？
: 也用不着dijkstra,就是简单的pre-order traversal就可以勒。
: inside a class:
: private List
: private int minSum = Integer.MAX_VALUE;
: private void minSumPathFromRootToLeave(BSTNode node,
: ArrayList
: //path is the path from root to node's parent,
: //currentSum is sum from root till node's parent
: // add base cases here:
z*w
33 楼
嗯，直接DFS就可以了O(V+E)
e*s
34 楼
请教大牛,
List 不是应该 pass by reference implicity吗?为什么要ref 在前面?
【在 p*****2 的大作中提到】
: 我写了个C#的，发现在纸上写好，到了VS上还是要改很多。
: static void minSum(Node root)
: {
: if (root == null)
: return;
: List list = new List();
: List minlist = new List();
: list.Add(root);
: Check(list, ref minlist);
: Console.WriteLine(minlist.Count-1);
List 不是应该 pass by reference implicity吗?为什么要ref 在前面?
【在 p*****2 的大作中提到】
: 我写了个C#的，发现在纸上写好，到了VS上还是要改很多。
: static void minSum(Node root)
: {
: if (root == null)
: return;
: List
: List
: list.Add(root);
: Check(list, ref minlist);
: Console.WriteLine(minlist.Count-1);
e*s
35 楼
我编译跑了一遍，不对啊。。。。。。
【在 p*****2 的大作中提到】
: 我写了个C#的，发现在纸上写好，到了VS上还是要改很多。
: static void minSum(Node root)
: {
: if (root == null)
: return;
: List list = new List();
: List minlist = new List();
: list.Add(root);
: Check(list, ref minlist);
: Console.WriteLine(minlist.Count-1);
【在 p*****2 的大作中提到】
: 我写了个C#的，发现在纸上写好，到了VS上还是要改很多。
: static void minSum(Node root)
: {
: if (root == null)
: return;
: List
: List
: list.Add(root);
: Check(list, ref minlist);
: Console.WriteLine(minlist.Count-1);
e*s
36 楼
要改这一句才对吧
minlist.Sum(n => n.Value) > list.Sum(n => n.Value)
【在 p*****2 的大作中提到】
: 我写了个C#的，发现在纸上写好，到了VS上还是要改很多。
: static void minSum(Node root)
: {
: if (root == null)
: return;
: List list = new List();
: List minlist = new List();
: list.Add(root);
: Check(list, ref minlist);
: Console.WriteLine(minlist.Count-1);
minlist.Sum(n => n.Value) > list.Sum(n => n.Value)
【在 p*****2 的大作中提到】
: 我写了个C#的，发现在纸上写好，到了VS上还是要改很多。
: static void minSum(Node root)
: {
: if (root == null)
: return;
: List
: List
: list.Add(root);
: Check(list, ref minlist);
: Console.WriteLine(minlist.Count-1);
相关阅读
485是否需要未婚公证？what would be a EVL for a student弱EB1求Sigma Xi的推荐人合作者的presentation算数吗？关于NIW的推荐信immediate eecs networking方向review等了3个月了，还要ＰＰ么？准备DIY，包子请教几个问题急问 petition letter 的长度485补材料1/31 EB1B approved, Dallas Centerlg绿卡排期到了，但是不能递交485怎样要审稿的证明信三个审稿机会（药物流行病学、药物安全性方向）DIY的petition letter里的称谓有关485身份的复印件EB1 如果不用pp，要花多少时间知道结果啊？引用太多怎么办申请材料是双面打印还是单面？abstract审稿意见怎么写?