w******j
发帖数: 185 | 1 来个java的吧，带parent pointer和不带的，preorder和inorder的
import java.util.NoSuchElementException;
import java.util.Stack;
public class BST {
private Node root;
private static class Node {
int key;
Node left, right, parent;
Node(int key) {
this.key = key;
}
}
public BST(){
}
public BSTIterator inorderIterator() {
return new InorderIterator();
}
public BSTIterator preorderIterator() {
return new PreorderI... 阅读全帖 |
|
s*****y
发帖数: 897 | 2 Construct Binary Tree From Inorder and Preorder/Postorder Traversal
const int MAX = 256;
// a fast lookup for inorder's element -> index
// binary tree's element must be in the range of [0, MAX-1]
int mapIndex[MAX];
void mapToIndices(int inorder[], int n) {
for (int i = 0; i < n; i++) {
assert(0 <= inorder[i] && inorder[i] <= MAX-1);
mapIndex[inorder[i]] = i;
}
}
// precondition: mapToIndices must be called before entry
Node *buildInorderPreorder(int in[], int pre[], int n, int offse... 阅读全帖 |
|
w*******u
发帖数: 267 | 3 Given preorder and inorder traversal of a tree, construct the binary tree.
Note:
You may assume that duplicates do not exist in the tree.
https://leetcode.com/problems/construct-binary-tree-from-preorder-and-
inorder-traversal/
————————————————————————————————————
我的解法
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
struct TreeNode* buildTree(int* preorder, int preorderSize, int* inorder,
int inorderSi... 阅读全帖 |
|
e***s
发帖数: 799 | 4 一个简单的construct BT with preorder and inorder.
这是1337code大哥的C++ code(递归部分）.
root->left = buildInorderPreorder(in, pre+1, i, offset);
root->right = buildInorderPreorder(in+i+1, pre+i+1, n-i-1, offset+i+1);
但是在C#中不在unsafe block里面不能用指针(我也不想用指针）。
有什么方法能写得这么简洁呢？
int[] linorder = new int[divider];
int[] lpreorder = new int[divider];
int[] rinorder = new int[n - divider - 1];
int[] rpreorder = new int[n - divider - 1];
for(int i = 0; i < divider... 阅读全帖 |
|
c**********e
发帖数: 2007 | 5 How about this one?
void inorder(vector& v, BinaryTreeNode* node) {
if(node) {
inorder(v, node->left);
v.push_back(node->data);
inorder(v, node->right);
}
}
bool equal(BinaryTreeNode* one, BinaryTreeNode* two) {
vector v1, v2;
inorder(v1, one);
inorder(v2, two);
return v1.equal(v2);
} |
|
c**********e
发帖数: 2007 | 6 How about this one?
void inorder(vector& v, BinaryTreeNode* node) {
if(node) {
inorder(v, node->left);
v.push_back(node->data);
inorder(v, node->right);
}
}
bool equal(BinaryTreeNode* one, BinaryTreeNode* two) {
vector v1, v2;
inorder(v1, one);
inorder(v2, two);
return v1.equal(v2);
} |
|
S**I
发帖数: 15689 | 7 ☆─────────────────────────────────────☆
gzou (gzou) 于 (Thu May 12 02:26:35 2011, 美东) 提到:
马上就要G on site了，
求祝福。
下面是从本版收集到的Google的试题，便于大家查询。
申明：有的附带有解释说明的，也来自于本版或者网络，大家自己看， 不保证真确
http://www.mitbbs.com/article_t1/JobHunting/31847453_0_1.html
本人ECE fresh PhD，背景是电路/EDA，跟G业务基本没什么关系
同学内部推荐的，很简单的一次电面就给了onsite
题都不难，但是自己没把握好机会，出了一些小bug。
总的感觉，出错就是硬伤，宁可从最简单的算法写起，也不能出错。
电面：
1，Skip list， http://en.wikipedia.org/wiki/Skip_list
写code实现struct skip_list * find(struct skip_list *head, int value)
2，sorted array... 阅读全帖 |
|
S**I
发帖数: 15689 | 8 ☆─────────────────────────────────────☆
gzou (gzou) 于 (Thu May 12 02:26:35 2011, 美东) 提到:
马上就要G on site了，
求祝福。
下面是从本版收集到的Google的试题，便于大家查询。
申明：有的附带有解释说明的，也来自于本版或者网络，大家自己看， 不保证真确
http://www.mitbbs.com/article_t1/JobHunting/31847453_0_1.html
本人ECE fresh PhD，背景是电路/EDA，跟G业务基本没什么关系
同学内部推荐的，很简单的一次电面就给了onsite
题都不难，但是自己没把握好机会，出了一些小bug。
总的感觉，出错就是硬伤，宁可从最简单的算法写起，也不能出错。
电面：
1，Skip list， http://en.wikipedia.org/wiki/Skip_list
写code实现struct skip_list * find(struct skip_list *head, int value)
2，sorted array... 阅读全帖 |
|
c**y
发帖数: 172 | 9 问题简单概述：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和... 阅读全帖 |
|
c*******t
发帖数: 123 | 10 帖个代码，c++,十几行。
bool findPairWithGivenSumInBST(TreeNode* root, int target){
stack inorder,rinorder;
TreeNode *lo=root,*hi=root;
bool move_lo=true,move_hi=true;
while(lo||hi||!inorder.empty()||!rinorder.empty()){
if(move_lo){
while(lo){inorder.push(lo);lo=lo->left;}
lo=inorder.top();inorder.pop();
}
if(move_hi){
while(hi){rinorder.push(hi);hi=hi->right;}
hi=rinorder.top();rinorder.pop();
}
... 阅读全帖 |
|
d****2
发帖数: 6250 | 11 preorder: 1 2 3 4 5
inorder: 3 2 4 1 5
root 1
left subtree preorder 2 3 4
left subtree inorder 3 2 4
right subtree preorder 5
right subtree inorder 5
recursively work on left subtree and right subtree with the known
preorder and inorder lists. |
|
c***s
发帖数: 192 | 12 O(N)空间的时候就是先inorder一遍。
但按照相同的思路，并不需要在inorder的时候保存所有的节点。
所以空间可以变为O(1).
比如：用O(N)空间的时候，你的node是存在数组里，然后scan一次这个数组，
但其实你scan这个数组的操作其实跟inorder traversal的顺序是一模一样的。
所以其实你不需要用一个数组来保存nodes，而是自己用inorder traversal scan一遍
就可以了。
所需要的空间就是需要一个额外的变量来保存上一个node。 |
|
c***s
发帖数: 192 | 13 O(N)空间的时候就是先inorder一遍。
但按照相同的思路，并不需要在inorder的时候保存所有的节点。
所以空间可以变为O(1).
比如：用O(N)空间的时候，你的node是存在数组里，然后scan一次这个数组，
但其实你scan这个数组的操作其实跟inorder traversal的顺序是一模一样的。
所以其实你不需要用一个数组来保存nodes，而是自己用inorder traversal scan一遍
就可以了。
所需要的空间就是需要一个额外的变量来保存上一个node。 |
|
B********t
发帖数: 147 | 14 是你自己弄错了吧。。
用preorder inorder的方法，T2就不是T1的subtree. preorder inorder的这种方法是
需要在node之间加一些special character的，以便知道哪些左 右子树为NULL.
T1：inorder: 0201034
T2: inorder: 0201030 |
|
o*q
发帖数: 630 | 15 # 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
... 阅读全帖 |
|
y****n
发帖数: 15 | 16 题目描述 Q4.8：
You have two very large binary trees: T1, with millions of nodes, and T2,
with hundreds of nodes. Create an algorithm to decide if T2 is a subtree of
T1.
书中的解法一：
If T2’s preorder traversal is a substring of T1’s preorder traversal, and
T2’s inorder traversal is a substring of T1’s inorder traversal, then T2
is a subtree of T1.
我感觉这个方法可能有问题。虽然通过preorder和inorder遍历，可以唯一的定义一棵
树。但是如果T2是T1的子树，遍历字符串S2是S1的子串，那么S2可能对应到S1的不同位
置。举例来说，下面两棵树就满足S2是S1的子串，但T2不是T1的子树。
请众位高手帮忙检查一下，是我的结果有问题，还是书中有错误，多谢！
... 阅读全帖 |
|
c*********t
发帖数: 2921 | 17 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就行了。
谢谢！ |
|
h**k
发帖数: 3368 | 18 用两个指针，一个从正常的inorder扫过去，
一个是从右往左开始的inorder（即每个树的访问顺序是右子树-根节点-左子树）扫过
去，两个相遇的时候就是median
基本原理：在正常的inorder遍历中，
假设当前访问的点是cur_node，则必然cur_node的左子树已经遍历完毕。如果cur_node
的右子树不为空，则下一个要访问的点是cur_node的右子树上的最小的节点；如果为空
，则需要返回cur_node的父节点，而如果cur_node是它的父亲的右子树 ，则cur_node
的父亲已经访问过，继续上朔，直到找到一个祖先，cur_node在他的左子树上，这个祖
先就是下一个要访问的节点。 |
|
y*********e
发帖数: 518 | 19 第一题，BST到链表，inorder traverse便是。
从链表到BST，可能产生的BST并不是原先的BST。因为可以有2个不同的BST产生出一样
的inorder traverse，所以反过来，只有inorder traverse并不能确定原先的BST。
若是array的话，这样就好了。每次取array的中点，做成一个node，然后左边的就是
left subtree，右边的就是right subtree，可以做成递归。
public Tree build(int[] array, int low, int high) {
if (low > high)
return null;
if (low == high)
return new Tree(array[low]);
int mid = low + ((high - low) >> 1);
Tree root = new Tree(array[mid]);
root.left = build(array, low, mid - 1);
root.r |
|
a********e
发帖数: 80 | 20 复杂度O(M*N)
这个矩阵就可以看成一个BST，根在右上角,左边一格是左儿子，下边一格是右儿子。左边元素比自己
小的是左子树的节点，下边元素比自己大的是右子树节点。
然后中序遍历BST就可以了。
void InOrder(int x, int y, int low, int high)
{
if ((x>=0) && (x=0) && (y
x][y]>=low))
{
InOrder(x, y-1, low, array[x][y]);
cout<
InOrder(x+1, y, array[x][y], high);
}
} |
|
b*******y
发帖数: 232 | 21 我觉得第四题的思路是这样的
记得preorder和inorder能完全决定一棵binary tree
那么现在有了preorder，只要找出所有的inorder的组合，就相当于找出了所有的
binary tree
例如preorder是 4 2 1 3 6 5 7
我们知道4是root，那么可以把4插到任何一个地方，例如 2 1 3 4 6 5 7
那么2 1 3是左子树的元素，6,5,7是右子树的元素；2和6分别是左右子树的root
再分别对左右子树做操作，这样可以recursively求出所有的inorder
already
set |
|
S**I
发帖数: 15689 | 22 ☆─────────────────────────────────────☆
sugarbear (sugarbear) 于 (Thu Apr 7 00:42:48 2011, 美东) 提到:
找 二叉树 两个最大的相同子树
没答上来。
见了四个，被拒了。 第二个是manager，后来主动写信跟我联系，说把我推荐给industry recruiting team，不知道是不是有转机？ 觉得industry recruiting应该更难吧？ 求祝福！
☆─────────────────────────────────────☆
boohockey (Pursuit of Dreams!) 于 (Thu Apr 7 10:27:03 2011, 美东) 提到:
bless
这道题有没有正解
industry recruiting team，不知道是不是有转机？ 觉得industry recruiting应该更
难吧？ 求祝福！
☆─────────────────────────────────────☆
grass (美丽人生) 于 (Thu Apr... 阅读全帖 |
|
i**********e
发帖数: 1145 | 23 不好意思，可能破坏你这道面试题了。
假设定义为 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 |
|
f*********i
发帖数: 197 | 24 可以把两个树A,B分别preorder,inorder遍历
然后问题就变成
longest common string in preorder[A], preorder[B] => string 1
longest common string in inorder[A], inorder[B] => string 2
最后再次longest common string in string 1，string 2
如果全部用KMP来做，时间复杂度O(n) |
|
c**y
发帖数: 172 | 25 brutal force复杂度是比较高，但是如果有duplicate的话，只能用brutal force吧。
我只是不理解为什么CC150和我贴的论坛上说只用InOrder和PreOrder就可以了。上面那
个反例说明只用InOrder和PreOrder不够的。另外一个问题是InOrder,PreOrder和
PostOrder是不是就可以了呢（对于没有duplicate的元素）？ |
|
|
c**y
发帖数: 172 | 27 多谢回复。迪迪的帖子证明了即便inorder，preorder，和postorder都用也是不行的。
关于如果允许使用特殊字符的话，好像只要一个就可以了，either inorder, preorder
或者postorder都可以。通过使用特殊字符，一个binary tree的信息可以被一个序列完
全复制和恢复。因此只要一个序列就可以了。例如
2
/ \
1 3
Inorder: (1)2(3)
Preorder: 21()3()
Postorder: ()1()32
多谢各位 |
|
b*****u
发帖数: 648 | 28 最近面过一个和这个相关的题：
一个bst里有重复节点，要求输出总共重复次数
本身很简单，inorder一边维护一个counter就行了。
附加问题：如果在bst里，很多其他方法都要调用inorder，怎样generalize inorder方法
答案是设计一个接口visitor |
|
x********u
发帖数: 1150 | 29 cc 150 上是用preorder and inorder, 同时加上sentinel to mark null node.
我觉得inorder是没有必要的.
感觉需要严格的数学证明.
如果tree T contains tree S, T's preorder (with sentinel to mark null) 的
string 肯定 contains S's preorder string.
反方向, 如果T's preorder string contains S's preorder string, 就一定能推出 "
tree T contains tree S"?
如果preorder+sentinel不足够的话, 能不能给个反例来说明 inorder是必须的. |
|
h******e
发帖数: 52 | 30 这个题需要用一个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
1<-3<-6<-12
r->r->l-l
save the array 1,3, 6, 12 and start from 1 and b... 阅读全帖 |
|
g*******y
发帖数: 1930 | 31 才三个包子。。。
我以前贴过用stack实现postorder的code
你搜一下呢
重建树的时候，postorder数组的最后一个是根，在inorder数组中搜索到这个根，
inorder数组中左边的就是左子树的集合，右边就是又子树。
两边子树的集合就确定下来了。递归的建立左子树，柚子树，再跟当前的根连接起来就
行了。 |
|
i**********e
发帖数: 1145 | 32 序列化（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。万一树... 阅读全帖 |
|
I**********s
发帖数: 441 | 33 问了1) 研究, 2) 多线程程序设计, 3) 任意无穷字符串流, 内存有限, 找出唯一一对
重复字符串, 这个我说了哈希表和外部排序, 但是面试人说有更好的办法(后来想也许
是bloom filter), 然后追问外部排序的细节到结束. 估计要挂 :(
总结: 面试既是技术活, 又是运气活.
无论如何, 把我的准备工作放下面, 攒点rp, 希望对大家有所帮助.
Interview Qs
Data Structures
1. Integer
- find number of 1s
- next largest smaller
- smallest larger number
- determine if is palindrom
- itoa, atoi
- add 2 numbers w/o using + or arithmetic operators
- implement *, -, / using only +
- find max of two numbers w/o co... 阅读全帖 |
|
c*********n
发帖数: 1057 | 34 2nd Phone
他问我的问题我都回答出来了啊
就记得让我怎么check BST，
我说了个以前自己复习的时候用的方法
然后他说能不能用inorder来做？
我说可以啊
然后叫我写code
我花了10分钟写了用stack的 inorder，然后每次都和last visited node做比较
也完全没有bug
我记得前面还有几个问题都回答的满好的
结束的时候面试官还说你回答的很好，我白高兴了 |
|
d****2
发帖数: 6250 | 35 struct tree_node {
int x;
tree_node *left;
tree_node *right;
};
tree_node *build_tree(const std::vector &preorder, int start1, int end1
, const std::vector &inorder, int start2, int end2) {
if (start1 > end1)
return NULL;
if (start1 == end1) {
tree_node *tn = new tree_node;
tn->x = preorder[start1];
tn->left = NULL;
tn->right = NULL;
return tn;
}
int pos;
for (pos = start2; pos <= end2; pos++)
if (inorder[pos] == preorder[start1])
|
|
I**A
发帖数: 2345 | 36 这个和地主那个，各有利弊，地主那个很好理解。。
这个有没有bug？我写了个java version，对某些树，不work, 帮着看看，哪儿的问题？
public static Node buildTree(int[] preorder, int start1, int[] inorder,
int start2, int len){
if(len<=0)
return null;
Node node = new Node(preorder[start1]);
int k;
for(k=start2; k
if(inorder[k] == preorder[start1])
break;
if(k==start2+len)
return null;
node |
|
i**********e
发帖数: 1145 | 37 leaf 之间最大的距离？不是很懂。leaf之间必须是同一个level的吗？如果不是同一个
level的应该怎样？
我知道preorder序列能重建BST。但inorder序列不能重建原来的那个BST吧。是不是
inorder序列建一个平衡的BST？
感谢你的补充题，我会研究研究下。
一些常见面试题的答案与总结 -
http://www.ihas1337code.com |
|
g*****x
发帖数: 799 | 38 如果是binary的话inorder+preorder或inorder+postorder
n-nary存(node, parent) pair貌似可以，不知道有什么更好的方法 |
|
z**z
发帖数: 222 | 39 二叉树的情况，左子树 inorder: node->left, node, node->right
右子树 inorder: node->right, node, node->left
这两个子树遍历相等就可以了吧
如果是N叉树的情况，正常遍历用level用queue比较简单，
判断对称有什么思路吗?? |
|
s*****n
发帖数: 5488 | 40 来自主题: JobHunting版 - 一道G老题 this should be open. you can either use
inorder travesal of bst and sequantial scan of arry
or
use
search each element in arry in bst.
or use
inorder traversal of bst and binary search of array |
|
s*****n
发帖数: 5488 | 41 来自主题: JobHunting版 - 一道G老题 this should be open. you can either use
inorder travesal of bst and sequantial scan of arry
or
use
search each element in arry in bst.
or
inorder traversal of bst and binary search of array |
|
c********t
发帖数: 5706 | 42 来自主题: JobHunting版 - 一道G老题 Great!
Let's assume bst contains m nodes and array has n elements.
For each of your solution, the complexity is
1.inorder travesal of bst and sequantial scan of arry
O(m+n)
2.use search each element in arry in bst.
O(n*lg(m))
3.use inorder traversal of bst and binary search of array
O(m*log(n))
Am I right? |
|
m**q
发帖数: 189 | 43 只看pop的两个值是不够的，比如getback上面举得例子。
两个树pop pre-order traversal pop的顺序都是1，2，3
guangyi说的看过程大概是可以的，或者就干脆最直接的
preorder + inorder 或者 postorder + inorder |
|
|
H***e
发帖数: 476 | 45 蒽
是的， 最坏是O(lgn)
但是总和是O(n)锕，就是泥打印出来整个inorder traversal,每条边被经过两次
就是inorder traversal的路径
balanced |
|
c*****r
发帖数: 108 | 46 来自主题: JobHunting版 - 电面犯二了 上面有个人说的inorder是我个人觉得最好的。 写一个interative的inorder
traversal，两个指针一起移动就可以了。
不过hashmap的方法写起来快，还保险 |
|
c***g
发帖数: 472 | 47 给定一个inorder和preorder构建一颗二叉树
如果，这里面有duplicated的元素，请问如何做？还是根本做不了？ 因为你无法在
inorder里面判断哪个是左树还是右树啊 |
|
c***g
发帖数: 472 | 48 给定一个inorder和preorder构建一颗二叉树
如果，这里面有duplicated的元素，请问如何做？还是根本做不了？ 因为你无法在
inorder里面判断哪个是左树还是右树啊 |
|
q********c
发帖数: 1774 | 49 你这个不是iterator， 而是traversal, 两个是不一样的.Iterator class 要有一个
current state 指向 current node, 每次执行 advance/++ (C++) 或者next(Java)操
作，返回下一个node. 所以inorder iterator 实际上就是找到下一个inorder node. |
|
l*****a
发帖数: 14598 | 50 这样好不好
有一道著名的题 find next node in InOrder Traverse.
Now we can implement it's opposite action.
find previous node in InOrder Traverse.
node * FindNthNode(node * root,int n)
{
if((root==null)||(n<=0)) return null;
find rightmost;
if(n==1) return rightmost;
node * current=rightmost;
for(int i=2;i<=n;i++)
{
current=GetInOrderPreNode(current);
if(current==null) return null;
}
return current;
} |
|
