请教一道面试题,关于tree的# JobHunting - 待字闺中
A*1
1 楼
我刚去买了个oscar food steamer，26.99。最后一分钟决定买的。打算做baby food用。
本来想买空气炸锅的，也没降价。
本来想买空气炸锅的，也没降价。
f*z
2 楼
Given:
Binary operators: +, *
Operands: postive integers
Tree1: *
|
-----
| |
+ 3
|
---
| |
1 2
First Array Representation Example:
PreOrder: * + 1 2 3
PostOrder: 1 2 + 3 *
输入一个preorder字符串,有运算符和数字,输出postorder.
请问如何实现?
Binary operators: +, *
Operands: postive integers
Tree1: *
|
-----
| |
+ 3
|
---
| |
1 2
First Array Representation Example:
PreOrder: * + 1 2 3
PostOrder: 1 2 + 3 *
输入一个preorder字符串,有运算符和数字,输出postorder.
请问如何实现?
l*s
3 楼
买过了就不想了
不忍心看下月的帐单哈
不忍心看下月的帐单哈
v*k
4 楼
用一组stack，扫描并记下从深到浅所有 * n n 或 + n n然后倒序打印
t*e
5 楼
听了leooo的推荐，
如愿以偿买了food processor。
顺带买了个包，把锅的预算花掉了。
用。
【在 A*********1 的大作中提到】
: 我刚去买了个oscar food steamer，26.99。最后一分钟决定买的。打算做baby food用。
: 本来想买空气炸锅的，也没降价。
如愿以偿买了food processor。
顺带买了个包，把锅的预算花掉了。
用。
【在 A*********1 的大作中提到】
: 我刚去买了个oscar food steamer，26.99。最后一分钟决定买的。打算做baby food用。
: 本来想买空气炸锅的，也没降价。
f*z
6 楼
能说具体点么?
一个子树只有有子树没有左子树的情况怎么处理呢?
诚心请教
【在 v*****k 的大作中提到】
: 用一组stack，扫描并记下从深到浅所有 * n n 或 + n n然后倒序打印
一个子树只有有子树没有左子树的情况怎么处理呢?
诚心请教
【在 v*****k 的大作中提到】
: 用一组stack，扫描并记下从深到浅所有 * n n 或 + n n然后倒序打印
M*n
7 楼
买了30几箱方便面，半价，差不多够明年一整年了。
v*k
8 楼
不可能啊。任何operator都一定有两个子树。否则算式怎么成立呢？
PreOrder: * + 1 2 3
PostOrder: 1 2 + 3 *
* push stack 0
+ push stack 1, null push stack 0
1 push stack 1
2 push stack 1
stack 1 has 3 elements, back to stack 0, 3 push stack 0
然后先打印stack 1 再打印stack 0
【在 f***z 的大作中提到】
: 能说具体点么?
: 一个子树只有有子树没有左子树的情况怎么处理呢?
: 诚心请教
PreOrder: * + 1 2 3
PostOrder: 1 2 + 3 *
* push stack 0
+ push stack 1, null push stack 0
1 push stack 1
2 push stack 1
stack 1 has 3 elements, back to stack 0, 3 push stack 0
然后先打印stack 1 再打印stack 0
【在 f***z 的大作中提到】
: 能说具体点么?
: 一个子树只有有子树没有左子树的情况怎么处理呢?
: 诚心请教
t*e
9 楼
有保质期吗？
【在 M**********n 的大作中提到】
: 买了30几箱方便面，半价，差不多够明年一整年了。
【在 M**********n 的大作中提到】
: 买了30几箱方便面，半价，差不多够明年一整年了。
f*z
10 楼
那 + + 1 * 2 3 4呢?要启动几个stack? 与运算符个数相同? 如何决定4放在哪个stack
已经怎么让1最先打印出来呢
【在 v*****k 的大作中提到】
: 不可能啊。任何operator都一定有两个子树。否则算式怎么成立呢？
: PreOrder: * + 1 2 3
: PostOrder: 1 2 + 3 *
: * push stack 0
: + push stack 1, null push stack 0
: 1 push stack 1
: 2 push stack 1
: stack 1 has 3 elements, back to stack 0, 3 push stack 0
: 然后先打印stack 1 再打印stack 0
A*1
11 楼
什么牌子的food processor？
等你谈感想。。。
【在 t*****e 的大作中提到】
: 听了leooo的推荐，
: 如愿以偿买了food processor。
: 顺带买了个包，把锅的预算花掉了。
:
: 用。
等你谈感想。。。
【在 t*****e 的大作中提到】
: 听了leooo的推荐，
: 如愿以偿买了food processor。
: 顺带买了个包，把锅的预算花掉了。
:
: 用。
d*h
12 楼
按照这个写法，出来的postorder 是 2 1 + 3 *
【在 v*****k 的大作中提到】
: 不可能啊。任何operator都一定有两个子树。否则算式怎么成立呢？
: PreOrder: * + 1 2 3
: PostOrder: 1 2 + 3 *
: * push stack 0
: + push stack 1, null push stack 0
: 1 push stack 1
: 2 push stack 1
: stack 1 has 3 elements, back to stack 0, 3 push stack 0
: 然后先打印stack 1 再打印stack 0
【在 v*****k 的大作中提到】
: 不可能啊。任何operator都一定有两个子树。否则算式怎么成立呢？
: PreOrder: * + 1 2 3
: PostOrder: 1 2 + 3 *
: * push stack 0
: + push stack 1, null push stack 0
: 1 push stack 1
: 2 push stack 1
: stack 1 has 3 elements, back to stack 0, 3 push stack 0
: 然后先打印stack 1 再打印stack 0
M*n
13 楼
保质期=最佳食用时期。排在最佳食用期后面还有次佳食用期。
超过保质期一段时间根本没事，不存放潮湿的地下室都没问题，国内店面买的馒头都是
过期面粉做的，成本低，大家不都吃得活蹦乱跳的，过保质期一段时间no problem，不
要太娇气。
amazon 2012年的吃的东西都还在卖呢。
【在 t*****e 的大作中提到】
: 有保质期吗？
超过保质期一段时间根本没事，不存放潮湿的地下室都没问题，国内店面买的馒头都是
过期面粉做的，成本低，大家不都吃得活蹦乱跳的，过保质期一段时间no problem，不
要太娇气。
amazon 2012年的吃的东西都还在卖呢。
【在 t*****e 的大作中提到】
: 有保质期吗？
x*i
14 楼
一个stack就够了
【在 v*****k 的大作中提到】
: 不可能啊。任何operator都一定有两个子树。否则算式怎么成立呢？
: PreOrder: * + 1 2 3
: PostOrder: 1 2 + 3 *
: * push stack 0
: + push stack 1, null push stack 0
: 1 push stack 1
: 2 push stack 1
: stack 1 has 3 elements, back to stack 0, 3 push stack 0
: 然后先打印stack 1 再打印stack 0
【在 v*****k 的大作中提到】
: 不可能啊。任何operator都一定有两个子树。否则算式怎么成立呢？
: PreOrder: * + 1 2 3
: PostOrder: 1 2 + 3 *
: * push stack 0
: + push stack 1, null push stack 0
: 1 push stack 1
: 2 push stack 1
: stack 1 has 3 elements, back to stack 0, 3 push stack 0
: 然后先打印stack 1 再打印stack 0
l*s
15 楼
这个是干粮
我还备两桶呢，10年没问题
【在 M**********n 的大作中提到】
: 保质期=最佳食用时期。排在最佳食用期后面还有次佳食用期。
: 超过保质期一段时间根本没事，不存放潮湿的地下室都没问题，国内店面买的馒头都是
: 过期面粉做的，成本低，大家不都吃得活蹦乱跳的，过保质期一段时间no problem，不
: 要太娇气。
: amazon 2012年的吃的东西都还在卖呢。
我还备两桶呢，10年没问题
【在 M**********n 的大作中提到】
: 保质期=最佳食用时期。排在最佳食用期后面还有次佳食用期。
: 超过保质期一段时间根本没事，不存放潮湿的地下室都没问题，国内店面买的馒头都是
: 过期面粉做的，成本低，大家不都吃得活蹦乱跳的，过保质期一段时间no problem，不
: 要太娇气。
: amazon 2012年的吃的东西都还在卖呢。
f*t
16 楼
用树实现不是很直观吗，为什么要用stack
B*1
17 楼
似乎用stack，用树都可以吧？2种不同的方法，不过树是很直观。
x*i
18 楼
贴一下我的code吧
string pre2post(string pre)
{
string temp, tmp_pos;
int i = 0;
stack ops;
while (i < pre.size())
{
temp = pre.substr(i,1);
if (pre[i]=='-' || pre[i]=='+' ||
pre[i]=='*' || pre[i]=='/')
{
ops.push(temp);
}
else {
while (!ops.empty() &&
!((tmp_pos=ops.top()).size()==1 &&
(tmp_pos[0]=='-' || tmp_pos[0]=='+' ||
tmp_pos[0]=='*' || tmp_pos[0]=='/')))
{
string t = tmp_pos;
ops.pop();
t.append(temp);
t.append(ops.top());
ops.pop();
temp = t;
}
ops.push(temp);
}
i++;
}
if (!ops.empty())
return ops.top();
else {
return "";
}
}
int main()
{
string pre1="-+1*23/-456";
cout<
}
output:
-+1*23/-456
123*+45-6/-
string pre2post(string pre)
{
string temp, tmp_pos;
int i = 0;
stack
while (i < pre.size())
{
temp = pre.substr(i,1);
if (pre[i]=='-' || pre[i]=='+' ||
pre[i]=='*' || pre[i]=='/')
{
ops.push(temp);
}
else {
while (!ops.empty() &&
!((tmp_pos=ops.top()).size()==1 &&
(tmp_pos[0]=='-' || tmp_pos[0]=='+' ||
tmp_pos[0]=='*' || tmp_pos[0]=='/')))
{
string t = tmp_pos;
ops.pop();
t.append(temp);
t.append(ops.top());
ops.pop();
temp = t;
}
ops.push(temp);
}
i++;
}
if (!ops.empty())
return ops.top();
else {
return "";
}
}
int main()
{
string pre1="-+1*23/-456";
cout<
}
output:
-+1*23/-456
123*+45-6/-
n*w
19 楼
java写的。可以递归。
public class recurivePre2Post {
final static int MUL = -1;
final static int ADD = -2;
public static void main(String[] args){
int[] expr1 = {MUL, ADD, 1, 2, 3};
int[] expr2 = {ADD, ADD, ADD, ADD, 1, 2, 3, MUL, MUL, 4, 5, 6, 7};
int[] expr3 = {MUL, 2, ADD, 1, MUL, 3, 4};
convert(expr1, 0);
System.out.println();
convert(expr2, 0);
System.out.println();
convert(expr3, 0);
}
public static int convert(int[] expr, int index){
if(index < 0 || expr == null || expr.length == 0) return -1;
if(index == expr.length)
return -1;
int i = 0, e = expr[index];
if(isOperator(e)){
i = convert(expr, index+1); //print the first number
i = convert(expr, i+1); //print the second number
printOperator(e); //print the operator
return i;
}
else{
System.out.print(e + " ");
return index;
}
}
public static boolean isOperator(int e){
if(e == ADD || e == MUL)
return true;
return false;
}
public static void printOperator(int e){
if(e == MUL)
System.out.print("* ");
else
System.out.print("+ ");
}
}
input:
* + 1 2 3
output:
1 2 + 3 *
input:
+ + + + 1 2 3 * * 4 5 6 7
output:
1 2 + 3 + 4 5 * 6 * + 7 +
input:
* 2 + 1 * 3 4
output:
2 1 3 4 * + *
【在 f***z 的大作中提到】
: Given:
: Binary operators: +, *
: Operands: postive integers
: Tree1: *
: |
: -----
: | |
: + 3
: |
: ---
public class recurivePre2Post {
final static int MUL = -1;
final static int ADD = -2;
public static void main(String[] args){
int[] expr1 = {MUL, ADD, 1, 2, 3};
int[] expr2 = {ADD, ADD, ADD, ADD, 1, 2, 3, MUL, MUL, 4, 5, 6, 7};
int[] expr3 = {MUL, 2, ADD, 1, MUL, 3, 4};
convert(expr1, 0);
System.out.println();
convert(expr2, 0);
System.out.println();
convert(expr3, 0);
}
public static int convert(int[] expr, int index){
if(index < 0 || expr == null || expr.length == 0) return -1;
if(index == expr.length)
return -1;
int i = 0, e = expr[index];
if(isOperator(e)){
i = convert(expr, index+1); //print the first number
i = convert(expr, i+1); //print the second number
printOperator(e); //print the operator
return i;
}
else{
System.out.print(e + " ");
return index;
}
}
public static boolean isOperator(int e){
if(e == ADD || e == MUL)
return true;
return false;
}
public static void printOperator(int e){
if(e == MUL)
System.out.print("* ");
else
System.out.print("+ ");
}
}
input:
* + 1 2 3
output:
1 2 + 3 *
input:
+ + + + 1 2 3 * * 4 5 6 7
output:
1 2 + 3 + 4 5 * 6 * + 7 +
input:
* 2 + 1 * 3 4
output:
2 1 3 4 * + *
【在 f***z 的大作中提到】
: Given:
: Binary operators: +, *
: Operands: postive integers
: Tree1: *
: |
: -----
: | |
: + 3
: |
: ---
r*n
20 楼
贴个tree的版本，不过空string对应空tree的时候，似乎空指针处理的有些ugly，求更
简洁版本。
struct BNode
{
char c;
BNode* left;
BNode* right;
BNode():c(0){}; //avoid uninitialized value for c
BNode(char _c):c(_c),left(NULL),right(NULL){};
};
void pre2bst(string pre, size_t& start, size_t len, BNode* &p)
{
if(start
p=new BNode(pre[start]);
size_t curr=start;
start++;
if(pre[curr]=='+'||pre[curr]=='-'||pre[curr]=='*'||pre[curr]=='/')
{
pre2bst(pre,start,len,p->left);
pre2bst(pre,start,len,p->right);
}
else
return;
}
}
void post_order(BNode* p)
{
if(!p)
return;
if(!p->c)//handle empty tree
return;
post_order(p->left);
post_order(p->right);
cout<c;
}
void pre2post(string pre)
{
size_t len=pre.size();
BNode* bst= new BNode();
size_t begin=0;
pre2bst(pre, begin, len, bst);
post_order(bst);
}
void test_pre2post()
{
string tst[]={"*+123", "++*321/23", ""};
size_t len=sizeof(tst)/sizeof(tst[0]);
for(size_t i=0; i
cout<cout<pre2post(tst[i]);
cout<
}
【在 x***i 的大作中提到】
: 贴一下我的code吧
: string pre2post(string pre)
: {
: string temp, tmp_pos;
: int i = 0;
: stack ops;
: while (i < pre.size())
: {
: temp = pre.substr(i,1);
: if (pre[i]=='-' || pre[i]=='+' ||
简洁版本。
struct BNode
{
char c;
BNode* left;
BNode* right;
BNode():c(0){}; //avoid uninitialized value for c
BNode(char _c):c(_c),left(NULL),right(NULL){};
};
void pre2bst(string pre, size_t& start, size_t len, BNode* &p)
{
if(start
p=new BNode(pre[start]);
size_t curr=start;
start++;
if(pre[curr]=='+'||pre[curr]=='-'||pre[curr]=='*'||pre[curr]=='/')
{
pre2bst(pre,start,len,p->left);
pre2bst(pre,start,len,p->right);
}
else
return;
}
}
void post_order(BNode* p)
{
if(!p)
return;
if(!p->c)//handle empty tree
return;
post_order(p->left);
post_order(p->right);
cout<
}
void pre2post(string pre)
{
size_t len=pre.size();
BNode* bst= new BNode();
size_t begin=0;
pre2bst(pre, begin, len, bst);
post_order(bst);
}
void test_pre2post()
{
string tst[]={"*+123", "++*321/23", ""};
size_t len=sizeof(tst)/sizeof(tst[0]);
for(size_t i=0; i
cout<cout<pre2post(tst[i]);
cout<
}
【在 x***i 的大作中提到】
: 贴一下我的code吧
: string pre2post(string pre)
: {
: string temp, tmp_pos;
: int i = 0;
: stack
: while (i < pre.size())
: {
: temp = pre.substr(i,1);
: if (pre[i]=='-' || pre[i]=='+' ||
d*l
21 楼
void pre2post()
{
char c;
while((c=cin.get())==' ');
if(c < '0' || c > '9') {
pre2post(); pre2post();
}
cout << c;
}
{
char c;
while((c=cin.get())==' ');
if(c < '0' || c > '9') {
pre2post(); pre2post();
}
cout << c;
}
c*e
22 楼
摆脱各位老大不要写那么长的code了，说明白思路就好了。
【在 r******n 的大作中提到】
: 贴个tree的版本，不过空string对应空tree的时候，似乎空指针处理的有些ugly，求更
: 简洁版本。
: struct BNode
: {
: char c;
: BNode* left;
: BNode* right;
: BNode():c(0){}; //avoid uninitialized value for c
: BNode(char _c):c(_c),left(NULL),right(NULL){};
: };
【在 r******n 的大作中提到】
: 贴个tree的版本，不过空string对应空tree的时候，似乎空指针处理的有些ugly，求更
: 简洁版本。
: struct BNode
: {
: char c;
: BNode* left;
: BNode* right;
: BNode():c(0){}; //avoid uninitialized value for c
: BNode(char _c):c(_c),left(NULL),right(NULL){};
: };
n*w
23 楼
用递归很简洁的。
如果a[i]是operator，从a[i+1]开始递归print左子树并返回左子树的最后一个元素的
index。然后从a[index+1]开始print右子树，最后打印operator。
伪码
print（arr[], index）{
if(arr[index] is operator){
i = print(arr, index+1);
i = print(arr, i+1);
print(arr[index]);
return i;
}
else{
print(arr[index]);
return index;
}
}
【在 c*****e 的大作中提到】
: 摆脱各位老大不要写那么长的code了，说明白思路就好了。
如果a[i]是operator，从a[i+1]开始递归print左子树并返回左子树的最后一个元素的
index。然后从a[index+1]开始print右子树，最后打印operator。
伪码
print（arr[], index）{
if(arr[index] is operator){
i = print(arr, index+1);
i = print(arr, i+1);
print(arr[index]);
return i;
}
else{
print(arr[index]);
return index;
}
}
【在 c*****e 的大作中提到】
: 摆脱各位老大不要写那么长的code了，说明白思路就好了。
相关阅读
每日阵痛又来了最近的TRAVEL学校没有签在最新的I-20 上,入境章也盖在旧的上面求助 H1b材料不错，来了个onsite interview有人知道SAS是不是不sponsor H1b有谁投过柴大妈的公司“尖子班”么？Amazon电面面经（1面和2面）401k现在一般match多少？无聊，在网上查工资Export Control License等了50多天都没下来算正常马？急问，在学校找个老师挂名做volunteer需要什么PAPEER WORK想起一个问题，fastest algorithm for sorting small data请教一个C++问题什么时候说我需要H1B?现在CS和统计，那个好找工作？南加vs中西部，该不该跳？h1b transfer 加急一问 (转载)急问：学校department A给办了H1，以后可以在另一个departmen昨天有人贴了个长list的编程题onsite之后多久能有结果？