Faculty Scholarly Productivity Index 只有07年的数据？没最新的么？# Immigration - 落地生根
m*a
1 楼
a*e
2 楼
以为很简单，却没让别人满意。
题目：有一个binary tree，打印从root到最大值那个node的路径。
我先用recursion找最大值那个node，然后再找路径。应该是有更简单的方法，但现场
想不出来。大牛们能指点一下嘛？多谢
题目：有一个binary tree，打印从root到最大值那个node的路径。
我先用recursion找最大值那个node，然后再找路径。应该是有更简单的方法，但现场
想不出来。大牛们能指点一下嘛？多谢
s*x
3 楼
a*e
4 楼
牛黄是牛的结石
【在 m**********a 的大作中提到】
: hot deal啊。
: http://www.popyard.com/cgi-mod/newspage.cgi?num=669179&r=0&v=0&j=0
【在 m**********a 的大作中提到】
: hot deal啊。
: http://www.popyard.com/cgi-mod/newspage.cgi?num=669179&r=0&v=0&j=0
k*r
5 楼
用dfs, 存一个最大值，还有一个path。
每次遇到更大的数值，更新结果为当前的path？
每次遇到更大的数值，更新结果为当前的path？
s*z
6 楼
yes, I just used this version
m*a
7 楼
估计美国屠宰场也就直接扔掉了
k*a
8 楼
copy path需要时间，lz的方法就挺好，面试官不满意那是被坑了
【在 k****r 的大作中提到】
: 用dfs, 存一个最大值，还有一个path。
: 每次遇到更大的数值，更新结果为当前的path？
【在 k****r 的大作中提到】
: 用dfs, 存一个最大值，还有一个path。
: 每次遇到更大的数值，更新结果为当前的path？
c*a
9 楼
这个指标是指每年发的文章？ 还是总共的文章？
【在 s**z 的大作中提到】
: yes, I just used this version
【在 s**z 的大作中提到】
: yes, I just used this version
m*a
10 楼
倒回国发了？ 哈哈
f*y
11 楼
post-order travesal，return the path to the current max in the subtree.
public static void maxPath(TreeNode root) {
if (root == null) return;
ArrayList path = get(root);
System.out.println(path);
}
public static ArrayList get(TreeNode root) {
if (root == null) return null;
ArrayList left = get(root.left);
ArrayList right = get(root.right);
ArrayList list;
if (left == null && right == null || (left == null || root.val >
left.get(0)) && (right == null || root.val > right.get(0))) {
list = new ArrayList();
}
else if (left != null && right != null) {
list = left.get(0) > right.get(0) ? left : right;
}
else {
list = left != null ? left : right;
}
list.add(root.val);
return list;
}
public static void maxPath(TreeNode root) {
if (root == null) return;
ArrayList
System.out.println(path);
}
public static ArrayList
if (root == null) return null;
ArrayList
ArrayList
ArrayList
if (left == null && right == null || (left == null || root.val >
left.get(0)) && (right == null || root.val > right.get(0))) {
list = new ArrayList
}
else if (left != null && right != null) {
list = left.get(0) > right.get(0) ? left : right;
}
else {
list = left != null ? left : right;
}
list.add(root.val);
return list;
}
m*l
12 楼
明天去宰牛场溜达溜达，没准在垃圾堆里能捡一大块呢，反正美国人也不懂这个。
要是美国人问我捡这个干啥？我咋说呢？
要是美国人问我捡这个干啥？我咋说呢？
k*4
13 楼
为什么要copy path，搞个引用传进去就行了
【在 k***a 的大作中提到】
: copy path需要时间，lz的方法就挺好，面试官不满意那是被坑了
【在 k***a 的大作中提到】
: copy path需要时间，lz的方法就挺好，面试官不满意那是被坑了
m*t
14 楼
牛黄不知道，牛鞭应该有。
k*r
15 楼
找到最大值，再找路径不也是需要时间的吗？
更新结果的频率也不会很大吧。case by case，不一定哪个更快，但说不定面试官等着
这个答案。
【在 k***a 的大作中提到】
: copy path需要时间，lz的方法就挺好，面试官不满意那是被坑了
更新结果的频率也不会很大吧。case by case，不一定哪个更快，但说不定面试官等着
这个答案。
【在 k***a 的大作中提到】
: copy path需要时间，lz的方法就挺好，面试官不满意那是被坑了
m*a
16 楼
牛鞭不值钱， 牛黄据说一克300+ rmb呢。
【在 m******t 的大作中提到】
: 牛黄不知道，牛鞭应该有。
【在 m******t 的大作中提到】
: 牛黄不知道，牛鞭应该有。
c*g
17 楼
不能直接设个global list 去存那个path 以及current 最大值么？遍历完了树，不管
怎么遍历的。更新最大值的时候，更新对应的path就可以了？我感觉自己simple
minded了。
怎么遍历的。更新最大值的时候，更新对应的path就可以了？我感觉自己simple
minded了。
i*n
18 楼
屠夫还真和淘金的有一拼
l*s
19 楼
A recursive solution. Returning the max value while building the List
bigPath.
private int printBigNodePath(TreeNode root, List bigPath)
{
if (root == null) return int.MinValue;
bigPath.Add(root);
List curLeftPath = new List();
List curRightPath = new List();
int leftBig = printBigNodePath(root.Left, curLeftPath);
int rightBig = printBigNodePath(root.Right, curRightPath);
if (leftBig > rightBig && leftBig > root.Value)
{
bigPath.AddRange(curLeftPath);
return leftBig;
}
if (rightBig > leftBig && rightBig > root.Value)
{
bigPath.AddRange(curRightPath);
return rightBig;
}
return root.Value;
}
bigPath.
private int printBigNodePath(TreeNode root, List
{
if (root == null) return int.MinValue;
bigPath.Add(root);
List
List
int leftBig = printBigNodePath(root.Left, curLeftPath);
int rightBig = printBigNodePath(root.Right, curRightPath);
if (leftBig > rightBig && leftBig > root.Value)
{
bigPath.AddRange(curLeftPath);
return leftBig;
}
if (rightBig > leftBig && rightBig > root.Value)
{
bigPath.AddRange(curRightPath);
return rightBig;
}
return root.Value;
}
m*a
20 楼
你这头像太有性格了。
【在 i******n 的大作中提到】
: 屠夫还真和淘金的有一拼
【在 i******n 的大作中提到】
: 屠夫还真和淘金的有一拼
a*e
21 楼
多谢大侠，请问这类问题在哪里能准备到或者看到呢？
i*n
22 楼
路色就要配一个路色的形象，抱歉，给大家添堵了。
【在 m**********a 的大作中提到】
: 你这头像太有性格了。
【在 m**********a 的大作中提到】
: 你这头像太有性格了。
c*n
23 楼
你这样说反映你对数遍历有基本的不清楚
遍历到每一个节点时， 只有一个 stack,（对应于路径）
比较大小时， 至少需要左右两个子树的返回值，
当然每一个 node 返回时只需要保留一个， 你可以扔掉不要的， 但你至少需要记住两
个 path variable, 重复使用而已。 概念上每个点的 路径还是要 “冷冻” 下来的
【在 k******4 的大作中提到】
: 为什么要copy path，搞个引用传进去就行了
遍历到每一个节点时， 只有一个 stack,（对应于路径）
比较大小时， 至少需要左右两个子树的返回值，
当然每一个 node 返回时只需要保留一个， 你可以扔掉不要的， 但你至少需要记住两
个 path variable, 重复使用而已。 概念上每个点的 路径还是要 “冷冻” 下来的
【在 k******4 的大作中提到】
: 为什么要copy path，搞个引用传进去就行了
h*e
24 楼
这个题需要用一个trick去记住当前相对与root的位置。
int max = int.MinValue, maxPos = 0;
Inorder(Node node, int pos)
{
if(node == null)
return;
Inorder(node.left, pos*2);
if(max < node.val)
{
max = node.val;
maxPos = pos;
}
Inorder(node.left, pos*2+1);
}
Now we get max and the maxPos associated with it.
Then divide the maxPos by 2 all the way to 0, for example,
maxPos = 25, we get
1r->r->l-l
save the array 1,3, 6, 12 and start from 1 and build up the path.
【在 c******n 的大作中提到】
: 你这样说反映你对数遍历有基本的不清楚
: 遍历到每一个节点时， 只有一个 stack,（对应于路径）
: 比较大小时， 至少需要左右两个子树的返回值，
: 当然每一个 node 返回时只需要保留一个， 你可以扔掉不要的， 但你至少需要记住两
: 个 path variable, 重复使用而已。 概念上每个点的 路径还是要 “冷冻” 下来的
int max = int.MinValue, maxPos = 0;
Inorder(Node node, int pos)
{
if(node == null)
return;
Inorder(node.left, pos*2);
if(max < node.val)
{
max = node.val;
maxPos = pos;
}
Inorder(node.left, pos*2+1);
}
Now we get max and the maxPos associated with it.
Then divide the maxPos by 2 all the way to 0, for example,
maxPos = 25, we get
1r->r->l-l
save the array 1,3, 6, 12 and start from 1 and build up the path.
【在 c******n 的大作中提到】
: 你这样说反映你对数遍历有基本的不清楚
: 遍历到每一个节点时， 只有一个 stack,（对应于路径）
: 比较大小时， 至少需要左右两个子树的返回值，
: 当然每一个 node 返回时只需要保留一个， 你可以扔掉不要的， 但你至少需要记住两
: 个 path variable, 重复使用而已。 概念上每个点的 路径还是要 “冷冻” 下来的
z*o
25 楼
保存最大路径需要拷贝，
传递的可以用reference
传递的可以用reference
y*i
26 楼
public List getMaxNodePath(TreeNode node){
List max = new ArrayList();
max.add(node.val);
List res = new ArrayList();
res.add("");
findMaxPath(node, max, "", res);
return res;
}
public void findMaxPath(TreeNode node, List max, String path,
List res){
if(node == null){
return;
}
path = path.equals("") ? node.val + "" : path + "," + node.val;
if(node.val > max.get(0)){
max.set(0, node.val);
res.set(0, path);
}
findMaxPath(node.left, max, path, res);
findMaxPath(node.right, max, path, res);
}
List
max.add(node.val);
List
res.add("");
findMaxPath(node, max, "", res);
return res;
}
public void findMaxPath(TreeNode node, List
List
if(node == null){
return;
}
path = path.equals("") ? node.val + "" : path + "," + node.val;
if(node.val > max.get(0)){
max.set(0, node.val);
res.set(0, path);
}
findMaxPath(node.left, max, path, res);
findMaxPath(node.right, max, path, res);
}
k*4
27 楼
你想复杂了。这题不用看左右两个子树的返回值，只要一路DFS下去，看到比目前最大
值大的点，更新一下path就可以了。的确更新path是要O(LgN)的时间，在非最差情况下
可以忽略不计。
dfs(TreeNode* node, vector& path, int& maxNode, vector&
maxNodePath) {
path.push_back(node->val);
if (node->val > maxNode) {
maxNode = node->val;
maxNodePath = path;
}
if (node->left) dfs(node->left, path, maxNode, maxNodePath);
if (node->right) dfs(node->right, path, maxNode, maxNodePath);
path.pop_back();
}
【在 c******n 的大作中提到】
: 你这样说反映你对数遍历有基本的不清楚
: 遍历到每一个节点时， 只有一个 stack,（对应于路径）
: 比较大小时， 至少需要左右两个子树的返回值，
: 当然每一个 node 返回时只需要保留一个， 你可以扔掉不要的， 但你至少需要记住两
: 个 path variable, 重复使用而已。 概念上每个点的 路径还是要 “冷冻” 下来的
值大的点，更新一下path就可以了。的确更新path是要O(LgN)的时间，在非最差情况下
可以忽略不计。
dfs(TreeNode* node, vector
maxNodePath) {
path.push_back(node->val);
if (node->val > maxNode) {
maxNode = node->val;
maxNodePath = path;
}
if (node->left) dfs(node->left, path, maxNode, maxNodePath);
if (node->right) dfs(node->right, path, maxNode, maxNodePath);
path.pop_back();
}
【在 c******n 的大作中提到】
: 你这样说反映你对数遍历有基本的不清楚
: 遍历到每一个节点时， 只有一个 stack,（对应于路径）
: 比较大小时， 至少需要左右两个子树的返回值，
: 当然每一个 node 返回时只需要保留一个， 你可以扔掉不要的， 但你至少需要记住两
: 个 path variable, 重复使用而已。 概念上每个点的 路径还是要 “冷冻” 下来的
f*e
28 楼
你这个path， 把所有的node 都放进去了吧。
【在 l******s 的大作中提到】
: A recursive solution. Returning the max value while building the List
: bigPath.
: private int printBigNodePath(TreeNode root, List bigPath)
: {
: if (root == null) return int.MinValue;
: bigPath.Add(root);
: List curLeftPath = new List();
: List curRightPath = new List();
: int leftBig = printBigNodePath(root.Left, curLeftPath);
: int rightBig = printBigNodePath(root.Right, curRightPath);
【在 l******s 的大作中提到】
: A recursive solution. Returning the max value while building the List
: bigPath.
: private int printBigNodePath(TreeNode root, List
: {
: if (root == null) return int.MinValue;
: bigPath.Add(root);
: List
: List
: int leftBig = printBigNodePath(root.Left, curLeftPath);
: int rightBig = printBigNodePath(root.Right, curRightPath);
l*s
29 楼
你这个“所有“是指？
【在 f**********e 的大作中提到】
: 你这个path， 把所有的node 都放进去了吧。
【在 f**********e 的大作中提到】
: 你这个path， 把所有的node 都放进去了吧。
f*e
30 楼
就是， 所有node都放都path 里
【在 l******s 的大作中提到】
: 你这个“所有“是指？
【在 l******s 的大作中提到】
: 你这个“所有“是指？
l*s
31 楼
不是所有Tree的Node，而只是这个Big Path的按次序的Node。
也许你是在问为什么存TreeNode而不是Int Value？
【在 f**********e 的大作中提到】
: 就是， 所有node都放都path 里
也许你是在问为什么存TreeNode而不是Int Value？
【在 f**********e 的大作中提到】
: 就是， 所有node都放都path 里
相关阅读
千万不要到我们学校－EB1B 通杀，J1不转H1,材料拖到最后一日11月底的RD的485. 上周做了SR。今天收到信。大家都向推荐人要CV吗NIW package 寄出了，顺便推荐一下我的律师结婚证原件还需要翻译吗？急，请各位大侠指点。复印件可以都是黑白的么？uscis睡昏了吗？485 停在1.19不动了。 RD1.23 急死了紧急求救！！！遇white trash!刘老这样评价，成功机会多大FPPls help to evaluate my EB1A eligibilityEAD 可以注册公司吗？NIW 求评估绿卡体检要空腹吗？求ISI帐号文章被牛杂志cite值得吹么？4月份最近报绿的不多，但是好像140开喷有了AP回国要准备点什么啊？EECS的国际烂会的审稿申请EB1B是否COUNT啊？有人想审这篇稿子吗？国内的期刊。(gone)