e*****e
发帖数: 1275 | 1 我觉得这题得用queue.
随便乱写了点，运行没有问题：
typedef struct bfs_binary_tree_info
{
binary_tree * parent;
//true for left child, false for right child
bool left_flag;
int * inorder;
int m;
int BFS_index;
}bfs_binary_tree_info;
binary_tree * build_binary_tree_from_inorder_BFS2 ( int inorder[], int m,
int BFS[], int BFS_index )
{
//verify input, make sure they are all valid
int root = BFS[BFS_index];
int root_in_index = -1;
queue tree_queue;
int... 阅读全帖 |
|
a***e
发帖数: 413 | 2 下面这两个1.2.写法都是O（N^2)吧？为啥2说是O（N）呢？另外，看到lc上一个
discussion的iterative的解法3.https://oj.leetcode.com/discuss/2297/the-
iterative-solution-is-easier-than-you-think
时间复杂度是O（N）吧？
我看了helper的function signature能写出1，对2中用到的好多STL要搜索才能写出来
，不熟。
Binary tree和recursion现在是我最弱处，多谢！
1.
class Solution {
public:
TreeNode *buildTree(vector &preorder, vector &inorder) {
if (preorder.size()==0) return NULL;
else if (preorder.size()==1)
{
TreeNode *t = new TreeNode(preorder[0])... 阅读全帖 |
|
g***j
发帖数: 1275 | 3 我这个全部通过了，多半是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... 阅读全帖 |
|
C*******a
发帖数: 448 | 4 以下是这道题正确的代码
然而当我想把代码简洁一些，把标有*的4行换成1行:
int i = Arrays.asList(inorder).indexOf(preorder[preL]);
就会报错。谁知道错在哪儿？？？
public class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
return _buildTree(preorder, 0, preorder.length, inorder, 0, inorder.
length);
}
private TreeNode _buildTree(int[] preorder, int preL, int preR, int[]
inorder, int inL, int inR) {
if (preL >= preR) {return null;}
TreeNode root = new TreeNode(preorder[preL]);
* int i... 阅读全帖 |
|
l**********1
发帖数: 415 | 5 写了个练手，求牛人指正
public static TreeNode rebuild(int[] inorder,int[] bfs,int bfsl,int bfsh,int
inorderl, inorderh){
//base case
if(bsfl>=bfsh||inorderl>inorderh) return null;
TreeNode root=new TreeNode();
root.value=bfs[bfsl];
//find the index of root value in inorder array
int cutoff=findCut(inorder,inorderl,inorderh,bfs[bfsl]);
//build the tree recursively
root.right=rebuild(inorder,bfs,bfsl+1,bfsh,inorderl,cutoff-1);
root.left=rebuild(inorder,bfs,bfsl+2,bfsh,cutoff+1,inorderh);
return root;
}
publi... 阅读全帖 |
|
i***e
发帖数: 452 | 6 我都试过你的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... 阅读全帖 |
|
t****n
发帖数: 19 | 7 死活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 | 8 死活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... 阅读全帖 |
|
w******j
发帖数: 185 | 9 来个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... 阅读全帖 |
|
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... 阅读全帖 |
|
y*********e
发帖数: 518 | 11
是BST嘛？假设是BST。
6
/ \
4 8
/ \ / \
1 5 7 9
inorder是 1 4 5 6 7 8 9
levelorder是 6 4 8 1 5 7 9
6
/ \
4 8
/ / \
1 7 9
inorder是 1 4 6 7 8 9
levelorder是 6 4 8 1 7 9
注意到，在 levelorder 中， INDEX (parent) < INDEX (node)。
解法思路如下：
1、取 levelorder 的第一个，作为 root。在 inorder 里面，小于 root 的值，是为
left sub tree。在 inorder 里面，大于root 的值，是为 right sub tree。
2、在 levelorder 里面找寻第一个值 n，使得 n < root && INDEX(n) >
INDEX(root) |
|
j******2
发帖数: 362 | 12 用跟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=... 阅读全帖 |
|
a***e
发帖数: 413 | 13 这个是在leetcode的讨论中一个叫dtx0的同学贴的。
gpraveenkumar的idea和他/她的几乎一样
The idea is as follows: 程序中没用flag，而是用pp这个指针
1) Keep pushing the nodes from the preorder into a stack (and keep making
the tree by adding nodes to the left of the previous node) until the top of
the stack matches the inorder.
2) At this point, pop the top of the stack until the top does not equal
inorder (keep a flag to note that you have made a pop).
3) Repeat 1 and 2 until preorder is empty. The key point is that whenever
the flag is set... 阅读全帖 |
|
a****s
发帖数: 22 | 14 不知道这样行不行, 感觉可以,不过没编译试过.基本意思就是Inorder遍历树，记住当
前节点的In-order上一个节点.
void FindInOrderNextInTreeHelper(Node *p, int data, Node *& next, Node *&
prev)
{
if(!p) return;
FindInOrderNextInTreeHelper(p->left, data, next, prev);
if(prev && prev->data == data)
{
next = p;
return;
}
prev = p;
FindInOrderNextInTreeHelper(p->right, data, next, prev);
}
Node * FindInOrderNextInTree(Node *p, int data)
{
if(!p) return NULL;
Node * next = NULL;
Node * prev =... 阅读全帖 |
|
h*******0
发帖数: 68 | 15 不知道这样行不行, 感觉可以,不过没编译试过.基本意思就是Inorder遍历树，记住当
前节点的In-order上一个节点.
void FindInOrderNextInTreeHelper(Node *p, int data, Node *& next, Node *&
prev)
{
if(!p) return;
FindInOrderNextInTreeHelper(p->left, data, next, prev);
if(prev && prev->data == data)
{
next = p;
return;
}
prev = p;
FindInOrderNextInTreeHelper(p->right, data, next, prev);
}
Node * FindInOrderNextInTree(Node *p, int data)
{
if(!p) return NULL;
Node * next = NULL;
Node * prev =... 阅读全帖 |
|
c******w
发帖数: 1108 | 16 preorder+inorder 和 BFS+inorder没有本质区别 |
|
i**********e
发帖数: 1145 | 17 你意思是从文件读取树，用 inorder 来重建树对吧？ |
|
p********7
发帖数: 549 | 18 怎么能写出比较好的代码呢？ 感觉复杂度比较高，不像inorder和preorder重建容易 |
|
p********7
发帖数: 549 | 19 主要是level的数是乱的，比如就是一个int数组，recursive每次还需要把左右2边的
levelorder
分开，需要每次都遍历一次inorder，复杂度比pre和in重建高很多 |
|
g*l
发帖数: 385 | 20 有 parent link比较容易, 要是没有 parent link, 是不是只能用 iterative inorder
traversal : 找到当前节点, 输出它的下一个? |
|
c******w
发帖数: 102 | 21 Node* nextNode(Node* root, int data)
{
Node* result = NULL;
while(root)
{
if( root->value > data )
{
result = root;
root = root -> left;
}
else
root = root -> right;
}
return result;
}
inorder |
|
g********d
发帖数: 203 | 22 BST or just binary tree?
inorder |
|
m*****e
发帖数: 47 | 23 If an inorder traversal on a binary tree gets the elements in sorted order,
does it necessarily prove it is a binary search tree? |
|
g*********s
发帖数: 1782 | 24 a bt is bst iff inorder travesal returns a strictly sorted array.
notice there's trap: if the bt has duplicate elements, it can't be a bst.
but if excluding duplicates, u can use mathematical induction to prove it.
order, |
|
C***y
发帖数: 2546 | 25 在 inorder sequence中找root node怎么搜索比较快？
我的想法是从中间，同时向两边linear search
还有什么更好的办法吗？ |
|
C***y
发帖数: 2546 | 26 一般情况下，root应该在inorder sequence中比较接近中间的地方 |
|
h*****g
发帖数: 312 | 27 7
/ \
8 9
\ / \
5 4 6
inorder: 857496
BFS: 789645
如何 重构这个二叉树，然后求树的宽度（哪一层node最多？） |
|
s******n
发帖数: 3946 | 28 楼上完全错误，不能用root分两段，这办法只适合preorder+inorder |
|
l**********1
发帖数: 415 | 29 请问为什么不能用root分两段？inorder不是所有左子树全在左边，右子树全在右边么
？ |
|
h*****y
发帖数: 218 | 30 题目没有看清楚
是BFS and inorder |
|
k*******r
发帖数: 355 | 31 虽然一个子树在BFS 序列中会不连续，但我觉得这道题还是可以模拟preorder+inorder
用递归做，唯一要额外注意的就是要把不连续的BFS串抽出来拼成连续串（以便这个连
续串对应一个子树）
code写起来也不麻烦，十几行吧，请高手指正
struct node{node * l,r; int id;}
node * f(int b[], int i[], int len){
if (len==0){return NULL}
node * h=new node; h->id=b[0]; h->l=NULL; h->r=NULL;
if (len==1){ return h;}
int k=findhead(b[0], i); map m;
int *newi=new int[k]; for (int j=0; j
int *newb=new int[k]; for (int j=0; j阅读全帖 |
|
p*****2
发帖数: 21240 | 32 看了看，感觉应该可以分两段。
BFS 可以看出7是root
indorder可以看出85是左树，496是右树
BFS又可以看出，8是左树的根，9是右树的根
7
/ \
8 9
\ / \
5 4 6
inorder: 857496
BFS: 789546 |
|
i**********e
发帖数: 1145 | 33 你好像忘了考虑当 node 是 subtree 中的最右边值 （也就是它的 next inorder 是返
回 subtree->parent)。 |
|
p*****2
发帖数: 21240 | 34
例如，一个 node 如果有 left node，直接返回 left-most node 即可
>>这个不是inorder吗？怎么会直接返回left-most?
只有在 node 是 leaf node 的情况之下 才需要从 root 开始
>>如果node没有right node的话也需要从root开始呀。
感觉只在node有right的情况呀，才能能直接返回吧？这种情况应该可以wrap一下就包
括了吧。一会儿看看。 |
|
i**********e
发帖数: 1145 | 35 不好意思，你是对的。
是next inorder，所以不看left subtree。
主要看有没有right child，有的话返回right subtree的 left most node。不然的话
得找出包含这个 node 为 right-most node 的subtree 的 parent，得用递归或者
stack（非递归） 来做。 |
|
c******t
发帖数: 391 | 36 debug了一下，貌似是那个Arrays.BinarySearch的问题，比如BinarySearch([2,1],1)
的结果是-1，因为不是有序的。 换成下面的搜索就可以了：
for(inorderRootPos = 0; inorder[inorderRootPos]!=rootVal; inorderRootPos++);
//empty loop body
my 2 cents :) |
|
c********t
发帖数: 5706 | 37 上次有人发了 postorder只用一个stack的iteration解法。 inorder有谁有解法？
我用了一个stack还用了一个size n 的hashmap，好像不太漂亮。 |
|
b***m
发帖数: 5987 | 38 我一般用这个：
void InOrder(Node *pRoot)
{
Stack s;
Node *pNode = pRoot;
while( pNode || !s.Empty() )
{
while( pNode )
{
s.push(pNode);
pNode = pNode->pLeft;
}
if( !s.Empty() )
{
pNode = s.pop();
Visit(pNode);
pNode = pNode->pRight;
}
}
} |
|
b***m
发帖数: 5987 | 39
对啊，PreOrder和InOrder我都用这套代码，把Visit换个地方就行，比较省事儿。;-) |
|
s**********e
发帖数: 326 | 40 昨天面的，面试官首先迟到了将近五分钟，上来面试官简单介绍了他自己，然后就直接
进入主题，也没有让我做自我介绍啥的，上来问我有没有用过java iterator pattern,
我给听成intepreter, 回答没用过，他不相信，又问了一遍，恍然大悟，赶紧说用过
用过，用过很多，然后他还说用java的人不可能没用过
然后问为什么用iterator, 有啥好处
答了之后接着问java里面有几种list, 答arraylist和linkedlist
又问实现这两种不同list的iterator有什么不同，到此为止都是对答如流，问他我答的
是不是他想要的答案，他说exactly
答完以后开始出题，先是写个data structure, 让我guess这是什么data structure,
class N {
private N l; // can be null
private N r; // can be null
private String data;
}
一紧张说成linkedlist, 赶紧改口说是tree,
然后就是描述问题，要求写一个Iterator, 每... 阅读全帖 |
|
s**********e
发帖数: 326 | 41 是的，这道题考察的就是如何设计iterator, 悲催的是iterator on binary tree, 而
且要求iterate的顺序必须是inorder. 设计iterator on array, linkedlist之类的要
比这个简单一些。即使iterate on binary tree in level order也要简单一些，对我
来说。应该算是一道集design和算法为一体的一道题吧。我面试之前是没有见到过这道
题，不知道是不是常见题。
trees |
|
s****y
发帖数: 44 | 42 MS on-site, A3问了这道题，结果挂了。CC150和recruiter都说见到最后一个
interviewer (HM的Manager)就差不多了。上次Amazon也是被A3灭了。
TreeNode CreateBinaryTree(int[] preorder, int[] inorder)
{
} |
|
w*****e
发帖数: 931 | 43 如果有duplicate number的话，preorder和inorder不能唯一确定BST吧。 |
|
z*********e
发帖数: 10149 | 44 如果preorder 是 abdac
inorder是dbaac
有两种可能的binary tree
一种是
a
/
b c
/
d a
另外一种是
a
/
b a
/
d c |
|
f*******w
发帖数: 1243 | 45 应该都是n^2吧。这两个方法好像没有任何区别啊。
除非find()还有什么特别的技巧？不过在没排序的vector里面查找肯定是O(n)了。
如果数组没重复的话，可以先把inorder存在hash里，key是数组里面的值，value是
index。这样能做到O(n) in time. |
|
y*********e
发帖数: 518 | 46 感觉对方是在问 Closure。
这个是 Java 对 Lambda 表达式的实现。Java 7 已经确定在语法上支持这个。
Java 6或者以前的版本只能靠 interface + anonymous class 来实现。
若是做过 functional programming（比如haskell），应该对 Lamdba 表达
式比较熟悉。
从C++的角度来看，就是 function pointer，但是它是 Strongly Typed。
举例代码来说明。假设要对二叉树遍历，代码很好写，比如：
void inOrder(Tree tree) {
if (tree != null) {
inOrder(tree.getLeft());
System.out.println(tree.getValue());
inOrder(tree.getRight());
}
}
但是如上的函数只是把Node的值打印到终端。若是要变得generic一点，要遍历的
过程中，能引入一个函数，对每一个Node执行这个函数，该多好。这样就引入了一
个概念：能... 阅读全帖 |
|
q*********u
发帖数: 280 | 47 【 以下文字转载自 JobHunting 讨论区 】
发信人: yinyueyouge (隐约有歌), 信区: JobHunting
标 题: Re: java enclosure是什么-今天被hm问倒了
发信站: BBS 未名空间站 (Fri Oct 22 09:27:57 2010, 美东)
感觉对方是在问 Closure。
这个是 Java 对 Lambda 表达式的实现。Java 7 已经确定在语法上支持这个。
Java 6或者以前的版本只能靠 interface + anonymous class 来实现。
若是做过 functional programming（比如haskell），应该对 Lamdba 表达
式比较熟悉。
从C++的角度来看，就是 function pointer，但是它是 Strongly Typed。
举例代码来说明。假设要对二叉树遍历，代码很好写，比如：
void inOrder(Tree tree) {
if (tree != null) {
inOrder(tree.getLeft());
System.out.p... 阅读全帖 |
|
n*p
发帖数: 298 | 48 in order traversal
要用一个变量来存前一个Node的值。但发现有时候值没有被更新，结果是错的，是因为
Java的passing by value的原因吗？代码如下：
public boolean isValidBST(TreeNode root) {
// Start typing your Java solution below
// DO NOT write main() function
if (root == null) return true;
//if (root.left == null && root.right == null) return true;
Integer preVal = Integer.MIN_VALUE;
return inOrder (root, preVal);
}
public boolean inOrder(TreeNode root, Integer preVal... 阅读全帖 |
|
h********s
发帖数: 66 | 49 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... 阅读全帖 |
|
f*********m
发帖数: 726 | 50 从版上大牛的面经中找到的：
---------------
1）原题can Jump, 然后拓展到minJump, 我用dp + greedy从左边做， 写完code,他要
求再说说从右边忘左边如何高。 我说还是dp + greedy（这个估计是他自己背的答案）
，他想了会说， 算了，好像跟你的一样！我也不知道是不是一样就move 到下一道题了。
从右往左好像不好想吧，从左往右跳（最后跳到最右边）和从右往左跳（最后跳到最左
边）不是等假的吧？
-------------
2）一个BST tree， 现在要求在每个node， 添加一个succeesor的指针。 用递归搞定
（这个在他提示下搞出的，code 用递归就几行而已）
考虑inorder 的succeesor。用inorder traverse，大家看对不对？
void inorder(node* n, node*& prev)
{
if (!n)
return;
inorder(n->left, prev);
if (!pre)
pre->succeesor = n;
pre = n;
inord... 阅读全帖 |
|
