g***j
发帖数: 1275 | 1 我这个全部通过了，多半是index的问题
class Solution {
public:
TreeNode *buildTree(vector &inorder, vector &postorder) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if(inorder.size() != postorder.size() ||
inorder.size() == 0 || postorder.size() == 0)
return NULL;
return buildTreeHelper(inorder, 0, inorder.size() - 1,
postorder, 0, postorder.size() - 1);
}
Tree... 阅读全帖 |
|
t****n
发帖数: 19 | 2 死活runtime error啊，在本地调试是可以的啊...囧了，有点怀疑是不是leetcode的问
题了..
Last executed input
[2,1], [2,1]
下面这个实现有什么问题么
public class Solution {
public TreeNode buildTree(int[] inorder, int[] postorder) {
if(inorder.length != postorder.length
|| inorder.length==0){
return null;
}
int rootVal = postorder[postorder.length-1];
int inorderRootPos = Arrays.binarySearch(inorder, rootVal);
TreeNode rootNode = new TreeNode(rootVal);
rootNo... 阅读全帖 |
|
t****n
发帖数: 19 | 3 死活runtime error啊，在本地调试是可以的啊...囧了，有点怀疑是不是leetcode的问
题了..
Last executed input
[2,1], [2,1]
下面这个实现有什么问题么
public class Solution {
public TreeNode buildTree(int[] inorder, int[] postorder) {
if(inorder.length != postorder.length
|| inorder.length==0){
return null;
}
int rootVal = postorder[postorder.length-1];
int inorderRootPos = Arrays.binarySearch(inorder, rootVal);
TreeNode rootNode = new TreeNode(rootVal);
rootNo... 阅读全帖 |
|
i***e
发帖数: 452 | 4 我都试过你的code， 可以过的啊。
给你贴个我写的吧 ：
TreeNode* help(vector& inorder, int startIndex, int n, vector&
postorder, int start2)
{
if(n < 1) return NULL;
TreeNode* root = new TreeNode(postorder[start2+n-1]);
if(n == 1) return root;
int index = startIndex;
for(;;index++)
if(inorder[index] == root->val)
break;
int l = index - startIndex;
root->left = help(inorder, startIndex, l, postorder,start2);
root->ri... 阅读全帖 |
|
j******2
发帖数: 362 | 5 用跟preorder+inorder construct tree类似的方法，死活过不了大的test，高手给指
点指点？
TreeNode *build(vector in, vector post, int in_start, int in_end,
int & post_index)
{
if(in_start>in_end)
{
return NULL;
}
TreeNode *r=new TreeNode(post[post_index--]);
if(in_start==in_end)
{
return r;
}
int in_index=search(in, in_start, in_end, r->val);
r->right=build(in, post, in_index+1, in_end, post_index);
r->left=... 阅读全帖 |
|
u*****o
发帖数: 1224 | 6 没错，postorder 是要往下走还是往回走需要判断，所以比其他两个难。。 |
|
|
a***e
发帖数: 413 | 8 牛。多谢！
但是我看了那个blog写的preorder和inorder OJ里面就是通不过，Inorder的弄到VS里
面debug半天，还是不知道哪里有问题，
Last executed input:
{1,2}
在VS里面能通过，不知道怎么回事。如果要问postorder Morris就简直太无语了，各位
有在面试中碰到的么？
vector inorderTraversal(TreeNode *root) {
vector ret;
TreeNode *r = root;
TreeNode *prev=NULL;
while(r!=NULL)
{
if(r->left==NULL)
{
ret.push_back(r->val);
r=r->right;
}
else
{
//find prede... 阅读全帖 |
|
a***e
发帖数: 413 | 9 如果要问postorder Morris就简直太无语了，各位有在面试中碰到的么？
而且这些东西感觉得面试前突击，不然久了不用容易忘吧？LC刷好几次的大牛们是不是
为这个目的？
我还一半都没刷完，sigh。 |
|
f********a
发帖数: 165 | 10 class Solution:
# @param inorder, a list of integers
# @param postorder, a list of integers
# @return a tree node
def buildTree(self, inorder, postorder):
n = len(inorder)
if n == 0:
return None
elif n == 1:
return TreeNode(postorder[-1])
else:
root = TreeNode(postorder[-1])
mid_inorder = inorder.index(postorder[-1])
root.left = self.buildTree(inorder[:mid_inorder], postorder[:mid
_inorder... 阅读全帖 |
|
h********s
发帖数: 66 | 11 Given inorder and postorder traversal of a tree, construct the binary tree.
觉得并不难，但是online judge之后，judge small能通过，judge large不通过，报
Runtime Error。下面是我的代码，高人能否分析下问题出在哪儿了。
public static TreeNode buildTree(int[] inorder, int[] postorder) {
// Start typing your Java solution below
// DO NOT write main() function
if(inorder.length==0 && postorder.length==0) return null;
int n = inorder.length;
int root_val = postorder[n-1];
TreeNode root = new TreeNode(r... 阅读全帖 |
|
c**y
发帖数: 172 | 12 问题简单概述：Binary Tree T1（大）和T2（小），判断T2是不是T1的substree。
CC150给的解法是对于每一个Tree，用InOrder和PreOrder的方法生成两个序列，然后判
断T2的两个序列是不是T1两个序列的substring。CC150还有brutal force的解法（这里
就不讨论了）。
我的问题是
1.这个序列比较的解法要求T1和T2不能有duplicate元素？这个应该是确定的，参见
http://www.geeksforgeeks.org/check-if-a-binary-tree-is-subtree-
2.为什么不比较PostOrder生成的序列呢？下面是一个反例（如果只用PreOrder和
InOrder
，返回True，但是实际应该是False）
T1:
1
/ \
2 3
\
4
T2:
1
/ \
2 3
T1:
InOrder: 2134
PreOrder: 1234
T2:
InOrder: 213
PreOrder: 123
如果只用InOrder和... 阅读全帖 |
|
x*****0
发帖数: 452 | 13 class Solution {
private:
TreeNode *pre;
public:
Solution() : pre(NULL) {}
void flatten(TreeNode *root) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
//static TreeNode* pre = NULL;
if (root != NULL) {
flatten(root->right);
flatten(root->left);
root->right = pre;
root->left = NULL;
pre = root;
}
}
};
各位帮我看看这段代码有什么问题？我自己测试leetcode给出的数据，没有问题。但是
就是过不了。
如果改... 阅读全帖 |
|
c*********t
发帖数: 2921 | 14 1. 如何用iterative 的方法实现postorder遍历binary tree？
recursive的方法太简单了。
好像inorder, preorder的iterative比较容易用stack就行了。可是postorder,我想不
出好的方法。谁能给个pseudo code?
2. 给定postorder 和 inorder遍历的结果，想个算法还原出binary tree.
3. 给定preorder 和 inorder遍历的结果，想个算法还原出binary tree.
我有三个包子，谁给回答对，就发包子给谁，一个包子一题。
给出pseudo code就行了。
谢谢！ |
|
c**y
发帖数: 172 | 15 多谢回复。迪迪的帖子证明了即便inorder，preorder，和postorder都用也是不行的。
关于如果允许使用特殊字符的话，好像只要一个就可以了，either inorder, preorder
或者postorder都可以。通过使用特殊字符，一个binary tree的信息可以被一个序列完
全复制和恢复。因此只要一个序列就可以了。例如
2
/ \
1 3
Inorder: (1)2(3)
Preorder: 21()3()
Postorder: ()1()32
多谢各位 |
|
b*****n
发帖数: 618 | 16 来自主题: JobHunting版 - RF 面经 姑且称为RF吧
申请的是fresh grad职位，2月底第一次跟hr联系到这个周拿到offer，中间经历了
online code test，onsite和一次电面。
好像不少人对他家的code test比较感兴趣，4个小时两道题，每个人遇到的题目可能不
一样，
第一题很简单，主要考察code质量，第二题稍微难一点，每个题目的要求都很详细要仔
细看，还有详细的提示也要注意。
我遇到的题：
1. 一个矩阵，从指定格子向右发射激光，每个格子有以下几种可能：激光直接穿过，
或者改变激光方向（4个方向）
问激光射出矩阵之前一共经过了多少格子，如果死循环了就输出－1
2. 一堆racer，每个racer有出发时间和到达时间，计算每个racer的score，规则如下
：score ＝ 所有出发比自己晚但是到达比自己早的racer数量之和，（所有的出发时间
和到达时间没有重复的）要求时间复杂度
code test过了之后我直接就安排onsite了，onsite本来安排6个人但实际上只面了5个
，题目如下：
1. 两个不一样长度的sorted array，求median。
leetcod... 阅读全帖 |
|
b*****n
发帖数: 618 | 17 来自主题: JobHunting版 - RF 面经 姑且称为RF吧
申请的是fresh grad职位，2月底第一次跟hr联系到这个周拿到offer，中间经历了
online code test，onsite和一次电面。
好像不少人对他家的code test比较感兴趣，4个小时两道题，每个人遇到的题目可能不
一样，
第一题很简单，主要考察code质量，第二题稍微难一点，每个题目的要求都很详细要仔
细看，还有详细的提示也要注意。
我遇到的题：
1. 一个矩阵，从指定格子向右发射激光，每个格子有以下几种可能：激光直接穿过，
或者改变激光方向（4个方向）
问激光射出矩阵之前一共经过了多少格子，如果死循环了就输出－1
2. 一堆racer，每个racer有出发时间和到达时间，计算每个racer的score，规则如下
：score ＝ 所有出发比自己晚但是到达比自己早的racer数量之和，（所有的出发时间
和到达时间没有重复的）要求时间复杂度
code test过了之后我直接就安排onsite了，onsite本来安排6个人但实际上只面了5个
，题目如下：
1. 两个不一样长度的sorted array，求median。
leetcod... 阅读全帖 |
|
g*******y
发帖数: 1930 | 18 才三个包子。。。
我以前贴过用stack实现postorder的code
你搜一下呢
重建树的时候，postorder数组的最后一个是根，在inorder数组中搜索到这个根，
inorder数组中左边的就是左子树的集合，右边就是又子树。
两边子树的集合就确定下来了。递归的建立左子树，柚子树，再跟当前的根连接起来就
行了。 |
|
i**********e
发帖数: 1145 | 19 应该是直接看图然后写出preorder，postorder and inorder的打印顺序。
如果要写出这三个非递归的代码有些残忍。
postorder 非递归不容易写(it is non-trivial)。
yingying1987:
非常谢谢你的分享，这些信息对我们都非常非常有用！在此感激不尽！恭喜你，you
deserve it!
狂赞 LZ 不放弃的态度：
小女子先后被ms, amazon,
vmware, nvidia, zynga, sig拒过，但从没放弃过。一定要从失败中获得教训，总结经
验，多来版上瞧瞧，胜利就在不远的前方。
一些常见面试题的答案与总结 -
http://www.ihas1337code.com |
|
f***z
发帖数: 65 | 20 Given:
Binary operators: +, *
Operands: postive integers
Tree1: *
|
-----
| |
+ 3
|
---
| |
1 2
First Array Representation Example:
PreOrder: * + 1 2 3
PostOrder: 1 2 + 3 *
输入一个preorder字符串,有运算符和数字,输出postorder.
请问如何实现? |
|
i**********e
发帖数: 1145 | 21 这题主要考察重建 general tree，不是 binary tree。然后就是怎么把 general tree
用 binary tree 来表示。
还有要注意给的是 preorder 和 postorder.在 binary tree 里 preorder 和
postorder 是不可能重建树的。
不过我认为这题作为面实题，给不到你对 candidate 很有用的signal。个人意见。 |
|
i**********e
发帖数: 1145 | 22 不好意思，可能破坏你这道面试题了。
假设定义为 general tree 的 postorder traversal 是遍历完current node的所有
children再遍历currentnode。
那么主要的trick是要发现 general tree (GT) 的 preorder 跟 binary tree
representation (BTR) 的 preorder 是一样的。另外，GT 的 postorder 和 BTR 的
inorder 遍历也是一样的。
所以重建树就成为了 BTR 的 preorder 和 inorder.
所以这题主要就利用经典的 preorder 和 inorder 遍历重建二叉树，然后再把 BTR 转化成 GT，不知道说对了没有？
http://www.cs.rutgers.edu/~kaplan/503/handouts/btreconNgentrees |
|
p*****2
发帖数: 21240 | 23 postorder?
def postorder(root):
f=0
n=root
while n!=None:
if f==2:
print n.val
if n.parent!=None and n==n.parent.left:
f=1
n=n.parent
elif f==1:
if n.right!=None:
f=0
n=n.right
else:
f=2
else:
if n.left!=None:
n=n.left
else:
f=1 |
|
K*********n
发帖数: 2852 | 24 实践一下或者搜一下代码就知道了，很别扭，细节很繁复，考虑需要特别周全。不像re
cursive版，三种order颠倒一下顺序就行了。
非recuesive版本，按照实现难度从易到难是preorder, inorder, postorder。
preorder随便写，inorder要仔细琢磨。如果面试碰到写postorder，我这水平基本上就
跪了。 |
|
|
c********t
发帖数: 5706 | 26 1. PostOrder和InOrder+特殊字符的方法是不是同样可行呢？
是
2. PreOrder，InOrder和PostOrder不加特殊字符的方法可以不可以呢？
不可以，见ls迪迪贴 |
|
c**y
发帖数: 172 | 27 多谢回复，还是有两个问题不明白，能否详细指教一下。
这个用特殊字符的方法一定要比较Both PreOrder（或者PostOrder）和InOrder的序列
吗？如果是的话，原因是什么呢？
啥是ls迪迪贴呀？另外问题2可能我没有表述清楚。我的意思是比较三个序列（分别由
InOrder，PreOrder和PostOrder Traversal的方法生成，但是不加任何特殊字符）。这
样三个序列不能唯一的确定一个Binary Tree吗？ |
|
s*********t
发帖数: 52 | 28 来自主题: JobHunting版 - 一个小面筋 电面一家最近比较火的startup
实现二叉树的postorder traversal，我就写啊，递归，很快搞定，十行左右，然后面
试官说不用写这么多四、五就能搞定，想了想也改好了。
follow up，不用递归，我就改啊，while循环，有个小错误，他提示之后，也写好了。
又follow up，在while循环的基础上，写getfirst函数，找到postorder的第一个node
指针，然后写个getnext函数，根据第一个接着一个一个找下去。我问能不能有额外内
存或者可不可以改变二叉树，比如删节点，回答说不行。然后就悲剧了，实在想不出
getnext怎么写，最后把getfirst写好就到时间了。现在想想，单向的二叉树不可能实
现吧？！嗨，当时应该多问一句是不是双向的。 |
|
f******n
发帖数: 198 | 29 不是，我是九月份做的，那时候才140题。我说的新题是说最上面的十几题。我记得FB
电面的时侯被问了BST postorder iterator, leetcode上还没有(而且之前所有的tree
的题目都没有postorder)。回来之后两天leetcode就加上了，估计最近比较流行吧:) |
|
h*****u
发帖数: 109 | 30 多位网友发过了，比如ultrabo，小节一下考点
A
/
B C
共六种排列 (要求): inorder, preorder, postorder, inorder right first (CAB),
preorder right first (ACB), postorder right first (CBA)
实现技术：recursive, iterative with one stack, iterative with two stacks,
iterative with parent pointer but no stacks, iterative with threaded binary
trees, Morris traversal (dynamic threaded tree)
做一个表，行是六种要求，列是各种技术，一共多少啊？还有没想到的吧。
Morris traversal codes: http://www.cnblogs.com/AnnieKim/archive/2013/06/15/MorrisTraversal.html |
|
I**********s
发帖数: 441 | 31 是啊, 如果BST, preorder/postorder之一就可以唯一确定结构. 如果是BT, 必须要
preorder+inorder, 或者postorder+inorder. |
|
|
o*q
发帖数: 630 | 33 # Title Editorial Acceptance Difficulty Frequency
1
Two Sum 28.3% Easy
292
Nim Game 54.4% Easy
344
Reverse String 57.3% Easy
136
Single Number 52.2% Easy
2
Add Two Numbers 25.6% Medium
371
Sum of Two Integers 51.6% Easy
4
Median of Two Sorted Arrays
20.4% Hard
6
ZigZag Conversion 25.6% Easy
13
Roman to Integer 42.7% Easy
237
... 阅读全帖 |
|
|
w********d
发帖数: 34 | 35 原帖。面经贴。
先报下背景，fresh cs master, 无牛实习，在学校一直跟着一个还不错的项目。
google给了我10.5w base+15% bonus+150 stock，不知道是个什么水平，但我已经很满
足了，准备从了。
第一个电面：
1. 比较hashtable和BST，神马时候用hashtable,神马时候用BST。各自的优势与缺点。
2. 那人在doc里粘了个BST的图，然后让我分别写下preorder, postorder和inorder。
然后问我已知这三个order的结果，能不能construct原本的bst。
3. 填这样一个函数 String reorder(String s, String order), 也就是要把s根据
order的顺序重新排序，然后返回。比如reorder("banana","na")应该返回"nnaab"。
order里没有出现的字母放在最后面就行了。
第二个电面：
1. 聊了一下我现在做的项目
2. 比较array和linked list的。
3. 两个linked list，如何找到intersect的那个node。
4. ... 阅读全帖 |
|
s***h
发帖数: 487 | 36 Recursive-function-call based graph traversal 跟 stack based graph traversal
在算法概念模型上有不少差别我想。
Recursive function call 是基于 non-overlapping subproblem 的编程概念。所谓
Preorder / inorder / postorder 就是 traverse non-overlapping subproblem 的
order。这个数学美，但有局限。
Stack 在编程概念上并不小矮挫，stack 的学名叫 LIFO ，对应的其他还有 FIFO，以
及更通用的 priority-queue (heap)。
: 不是叫iteration based traversal么？我没看哪个刷题网上用stack based来讲
，再说
: 了recursive的原理上不还是stack based么？只不过这个stack不用你费脑筋去
管理而
: 已。
|
|
s***h
发帖数: 487 | 37 当然对 graph 而不是 tree，subproblem 之间其实有 overlap，但这个 overlap 属于
trivial，用个 visited mark 先到先占位就是了。
: Recursive-function-call based graph traversal 跟 stack based graph
traversal
: 在算法概念模型上有不少差别我想。
: Recursive function call 是基于 non-overlapping subproblem 的编程概念。
所谓
: Preorder / inorder / postorder 就是 traverse non-overlapping
subproblem 的
: order。这个数学美，但有局限。
: Stack 在编程概念上并不小矮挫，stack 的学名叫 LIFO ，对应的其他还有
FIFO，以
: 及更通用的 priority-queue (heap)。
: ，再说
: 管理而
|
|
发帖数: 1 | 38 都是一样的
一个把stack放到代码段
一个把stack放到数据段
程序写法不太一样而已
: Recursive-function-call based graph traversal 跟 stack based graph
traversal
: 在算法概念模型上有不少差别我想。
: Recursive function call 是基于 non-overlapping subproblem 的编程概念。
所谓
: Preorder / inorder / postorder 就是 traverse non-overlapping
subproblem 的
: order。这个数学美，但有局限。
: Stack 在编程概念上并不小矮挫，stack 的学名叫 LIFO ，对应的其他还有
FIFO，以
: 及更通用的 priority-queue (heap)。
: ，再说
: 管理而
|
|
|
发帖数: 1 | 40 2.第一轮：亚裔（听名字不像中国人？） 一堆人参加比赛，最开始谁和谁先比是确
定的，比赛是两两配对，一轮一轮进行，print出若有round和可能的组合。比如 有
ABCD四个人比赛， 那结果是：
1 A - B
1 C - D.鏈枃鍘熷垱鑷�1point3acres璁哄潧
2 A - C
2 A - D
2 B - C
2 B - D
但是要考虑一个情况，就是有五个人比赛，比如 ABCDE五个人， 那么E这个人可能是在
C和D比完后和他俩的胜者比，或者E 和 AB的胜者比。或者E 和 ABCD的胜者比。
问题：1.用什么数据结构存比赛者。 就说二叉树就行了，把比赛者存在叶子节点，怎
么构成不需要你考虑。
2. print出结果（应该就是postorder traversal了）
有没有人能给出代码？ |
|
f*********r
发帖数: 68 | 41 use standard techniques to convert the recursive function to non-recursive
function. almost same as in and pre orders.
void postOrder() {
Node *p = root, *pre = root;
stack st;
int i = 0;
while(!st.empty() || p){
while(p){
st.push(p);
p = p->left;
}
p = st.top();
if(p->right == NULL || p->right == pre) {
visit(p);
st.pop();
pre = p;
p = NULL;
}
else
|
|
g*******y
发帖数: 1930 | 42 void FindLeftmostLeaf(Node *root, stack &stk){
while(root->left || root->right){ //while(当前节点不是叶子)
stk.push(root);
if (root->left){
root = root->left;
}else{
root = root->right;
}
}
stk.push(root);
}
void PostOrder(Node *root){
if(root) return; //check empty tree;
stack stk;
Node *node=root, *parent;
//找子树中最左边的叶子，并把途中的节点放入栈
FindLeftmostLeaf(root,stk);
while(!stk.empty()){
node |
|
i**********e
发帖数: 1145 | 43 序列化（Serialization）真的很有用，例如我在网站实现这个 online judge 就有用
到。ie，怎么把 binary tree，linked list，array 的函数传递参数等用 string 的
形式打印出来。
http://www.ihas1337code.com/onlinejudge
序列化 (Serialization) 二叉树是 amazon 常问题。可以好几种方法实现。
1） preorder/postorder/levelorder + inorder. 这前提是树里不能有任何重复值，
否则会有 ambiguity. 给个例子：
preorder = {7, 7}
inorder = {7, 7}
http://www.ihas1337code.com/2011/04/construct-binary-tree-from-
2）preorder/level order traverse + mark sentinel. 这个用一个 preorder
traversal 就能完成，很简单。但是缺点就是要利用一个 sentinel 来 mark。万一树... 阅读全帖 |
|
d****n
发帖数: 233 | 44 Do postorder traversal without using recursion.
You can't modify the tree node struct which is as following:
struct Node {
int data;
Node *left;
Node *right;
}
If you want to use stack, use no more than 1 stack.
Any idea?: |
|
B*****t
发帖数: 335 | 45 贴个代码仅供参考
void postOrder() {
Node *p = root, *visited = root;
stack st;
int i = 0;
while(!st.empty() || p){
while(p){
st.push(p);
p = p->left;
}
p = st.top();
if(p->right == NULL || p->right == visited) {
visit(p->c);
st.pop();
visited = p;
p = NULL;
}
else
p = p->right;
}
} |
|
I**A
发帖数: 2345 | 46 不知道哪个更好理解，自己看吧
//POSTORDER traversal iteratively
public static void postOrderIteratively(BST mybst){
Stack nodestack = new Stack();
Node node = mybst.root;
Node prevnode = mybst.root;
//initialize the stack
while(node!=null){
nodestack.push(node);
node = node.left;
}
while( !nodestack.isEmpty()){
node = (Node)nodestack.pop();
//if this is the leaf node, then print the data o |
|
y*********e
发帖数: 518 | 47 贴一贴代码 ：）
void postorder(const Node* node) {
std::stack stack;
while (node != NULL || !stack.empty()) {
if (node == NULL) {
while (!stack.empty() && node == stack.top()->right) {
node = stack.top(); stack.pop();
process(node->value);
}
node = stack.empty() ? NULL : stack.top()->right;
}
if (node != NULL) {
stack.push(node);
node = node->left;
}
}
} |
|
c***2
发帖数: 838 | 48 I can do it manually. But can't get an elegant program in C.
Does Anybody know a good solution?
Thanks, |
|
c***2
发帖数: 838 | 49 This one works, but looks ugly. |
|
c***2
发帖数: 838 | 50 Assume total nodes <= 16. |
|
