G*0
2 楼
大家都这样么？
我用的是Time Warner cable
我用的是Time Warner cable
l*a
3 楼
为什么内部不能存一个stack?
【在 z*********8 的大作中提到】
: 我估计不能在内部存一个stack吧， 是不是可以加个parent pointer？如果不能改，怎
: 么做？
【在 z*********8 的大作中提到】
: 我估计不能在内部存一个stack吧， 是不是可以加个parent pointer？如果不能改，怎
: 么做？
a9
4 楼
对，有好些个twc的抱怨了
【在 G**0 的大作中提到】
: 大家都这样么？
: 我用的是Time Warner cable
【在 G**0 的大作中提到】
: 大家都这样么？
: 我用的是Time Warner cable
z*8
5 楼
请问怎么做？
我想的作弊方法就是在constructor里面直接inorder recursion走一遍把所有node存到
stack里面。。。
【在 l*****a 的大作中提到】
: 为什么内部不能存一个stack?
我想的作弊方法就是在constructor里面直接inorder recursion走一遍把所有node存到
stack里面。。。
【在 l*****a 的大作中提到】
: 为什么内部不能存一个stack?
l*a
6 楼
你全存进去有点过分了。
不能只存部分吗？然后每步HasNext()用find next node for in-order traverse
实现不可以吗
【在 z*********8 的大作中提到】
: 请问怎么做？
: 我想的作弊方法就是在constructor里面直接inorder recursion走一遍把所有node存到
: stack里面。。。
不能只存部分吗？然后每步HasNext()用find next node for in-order traverse
实现不可以吗
【在 z*********8 的大作中提到】
: 请问怎么做？
: 我想的作弊方法就是在constructor里面直接inorder recursion走一遍把所有node存到
: stack里面。。。
g*e
7 楼
不用stack没法做吧
z*8
8 楼
我直接应该这么做， 但是不会写啊
求代码！
【在 l*****a 的大作中提到】
: 你全存进去有点过分了。
: 不能只存部分吗？然后每步HasNext()用find next node for in-order traverse
: 实现不可以吗
求代码！
【在 l*****a 的大作中提到】
: 你全存进去有点过分了。
: 不能只存部分吗？然后每步HasNext()用find next node for in-order traverse
: 实现不可以吗
l*a
9 楼
有MSFT L61 offer的这都不会写？
sde OR sdet?
【在 z*********8 的大作中提到】
: 我直接应该这么做， 但是不会写啊
: 求代码！
sde OR sdet?
【在 z*********8 的大作中提到】
: 我直接应该这么做， 但是不会写啊
: 求代码！
z*8
10 楼
janitor
【在 l*****a 的大作中提到】
: 有MSFT L61 offer的这都不会写？
: sde OR sdet?
【在 l*****a 的大作中提到】
: 有MSFT L61 offer的这都不会写？
: sde OR sdet?
p*2
11 楼
好多简单题也没练过。赶紧写一个练练。
import java.io.*;
import java.util.*;
public class test
{
public static void main(String[] args)
{
new test().run();
}
PrintWriter out = null;
void run()
{
Scanner in = new Scanner(System.in);
out = new PrintWriter(System.out);
Node node4 = new Node(4, null, null);
Node node5 = new Node(5, null, null);
Node node2 = new Node(2, node4, node5);
Node node6 = new Node(6, null, null);
Node node7 = new Node(7, null, null);
Node node3 = new Node(3, node6, node7);
Node root = new Node(1, node2, node3);
HashSet visited = new HashSet();
Stack stack = new Stack();
stack.add(root);
while (!stack.isEmpty())
{
Node node = stack.pop();
if (visited.contains(node))
out.println(node.value);
else
{
visited.add(node);
if (node.right != null)
stack.add(node.right);
stack.add(node);
if (node.left != null)
stack.add(node.left);
}
}
out.close();
}
}
class Node
{
Node left = null;
Node right = null;
int value;
public Node(int v, Node l, Node r)
{
value = v;
left = l;
right = r;
}
}
import java.io.*;
import java.util.*;
public class test
{
public static void main(String[] args)
{
new test().run();
}
PrintWriter out = null;
void run()
{
Scanner in = new Scanner(System.in);
out = new PrintWriter(System.out);
Node node4 = new Node(4, null, null);
Node node5 = new Node(5, null, null);
Node node2 = new Node(2, node4, node5);
Node node6 = new Node(6, null, null);
Node node7 = new Node(7, null, null);
Node node3 = new Node(3, node6, node7);
Node root = new Node(1, node2, node3);
HashSet
Stack
stack.add(root);
while (!stack.isEmpty())
{
Node node = stack.pop();
if (visited.contains(node))
out.println(node.value);
else
{
visited.add(node);
if (node.right != null)
stack.add(node.right);
stack.add(node);
if (node.left != null)
stack.add(node.left);
}
}
out.close();
}
}
class Node
{
Node left = null;
Node right = null;
int value;
public Node(int v, Node l, Node r)
{
value = v;
left = l;
right = r;
}
}
z*8
12 楼
我已经知道怎么写了， 不过你这个。。。
iterator应该提供hasNext和Next吧
【在 p*****2 的大作中提到】
: 好多简单题也没练过。赶紧写一个练练。
: import java.io.*;
: import java.util.*;
: public class test
: {
: public static void main(String[] args)
: {
: new test().run();
: }
: PrintWriter out = null;
iterator应该提供hasNext和Next吧
【在 p*****2 的大作中提到】
: 好多简单题也没练过。赶紧写一个练练。
: import java.io.*;
: import java.util.*;
: public class test
: {
: public static void main(String[] args)
: {
: new test().run();
: }
: PrintWriter out = null;
p*2
13 楼
啥意思？跟iterator什么关系？
【在 z*********8 的大作中提到】
: 我已经知道怎么写了， 不过你这个。。。
: iterator应该提供hasNext和Next吧
l*a
14 楼
天资聪颖的JANITOR
这么快就会了
【在 z*********8 的大作中提到】
: 我已经知道怎么写了， 不过你这个。。。
: iterator应该提供hasNext和Next吧
这么快就会了
【在 z*********8 的大作中提到】
: 我已经知道怎么写了， 不过你这个。。。
: iterator应该提供hasNext和Next吧
z*8
15 楼
http://docs.oracle.com/javase/1.4.2/docs/api/java/util/Iterator
【在 p*****2 的大作中提到】
:
: 啥意思？跟iterator什么关系？
【在 p*****2 的大作中提到】
:
: 啥意思？跟iterator什么关系？
p*2
16 楼
跟这道题又什么关系呢？
【在 z*********8 的大作中提到】
: http://docs.oracle.com/javase/1.4.2/docs/api/java/util/Iterator
z*8
17 楼
意思是每次调用next， 打印出来的节点顺序应该和inorder traversal一样
【在 p*****2 的大作中提到】
:
: 跟这道题又什么关系呢？
【在 p*****2 的大作中提到】
:
: 跟这道题又什么关系呢？
p*2
18 楼
明白了。没看清除题目。
【在 z*********8 的大作中提到】
: 意思是每次调用next， 打印出来的节点顺序应该和inorder traversal一样
b*e
19 楼
you need a parent pointer if you don't use stack.
In case of parent pionter, just call getNextBig to get next
【在 z*********8 的大作中提到】
: 我估计不能在内部存一个stack吧， 是不是可以加个parent pointer？如果不能改，怎
: 么做？
In case of parent pionter, just call getNextBig to get next
【在 z*********8 的大作中提到】
: 我估计不能在内部存一个stack吧， 是不是可以加个parent pointer？如果不能改，怎
: 么做？
h*e
20 楼
这道题看起来简单，用stack实现起来还是有一些小tricks的，例如
要记录那些结点已经被访问过了，减少不必要的压栈出栈操作等。
下面是我写的代码：
class SNode {
Node node;
boolean visited = false;
public SNode(Node n) {
node = n;
}
}
class BinaryTreeIterator {
Stack stack = new Stack();
public BinaryTreeIterator(Node root) {
SNode s = new SNode(root);
stack.push(s);
}
public boolean hasNext() {
return !stack.empty();
}
public Node next() {
SNode s = stack.pop();
do {
if (s.visited) {
return s.node;
}
// s is not visited yet
if (s.node.right!=null) {
stack.push(new SNode(s.node.right));
}
s.visited = true;
if (s.node.left==null) {
return s.node;
}
stack.push(s);
s = new SNode(s.node.left);
} while (true);
}
}
要记录那些结点已经被访问过了，减少不必要的压栈出栈操作等。
下面是我写的代码：
class SNode {
Node node;
boolean visited = false;
public SNode(Node n) {
node = n;
}
}
class BinaryTreeIterator {
Stack
public BinaryTreeIterator(Node root) {
SNode s = new SNode(root);
stack.push(s);
}
public boolean hasNext() {
return !stack.empty();
}
public Node next() {
SNode s = stack.pop();
do {
if (s.visited) {
return s.node;
}
// s is not visited yet
if (s.node.right!=null) {
stack.push(new SNode(s.node.right));
}
s.visited = true;
if (s.node.left==null) {
return s.node;
}
stack.push(s);
s = new SNode(s.node.left);
} while (true);
}
}
l*a
21 楼
没细看，但是想不出来为什么要有个visited的flag
简单说这题就是find in-order traverse next node
or find next big in BST
【在 h****e 的大作中提到】
: 这道题看起来简单，用stack实现起来还是有一些小tricks的，例如
: 要记录那些结点已经被访问过了，减少不必要的压栈出栈操作等。
: 下面是我写的代码：
: class SNode {
: Node node;
: boolean visited = false;
: public SNode(Node n) {
: node = n;
: }
: }
简单说这题就是find in-order traverse next node
or find next big in BST
【在 h****e 的大作中提到】
: 这道题看起来简单，用stack实现起来还是有一些小tricks的，例如
: 要记录那些结点已经被访问过了，减少不必要的压栈出栈操作等。
: 下面是我写的代码：
: class SNode {
: Node node;
: boolean visited = false;
: public SNode(Node n) {
: node = n;
: }
: }
p*2
22 楼
我也用了visited, 不过这题我以前没做过，不一定是最优。
【在 l*****a 的大作中提到】
: 没细看，但是想不出来为什么要有个visited的flag
: 简单说这题就是find in-order traverse next node
: or find next big in BST
h*e
23 楼
没有visited flag的话，同一个结点可能反复压栈。peking2的code
用了HashSet也是一样的道理。
【在 l*****a 的大作中提到】
: 没细看，但是想不出来为什么要有个visited的flag
: 简单说这题就是find in-order traverse next node
: or find next big in BST
用了HashSet
【在 l*****a 的大作中提到】
: 没细看，但是想不出来为什么要有个visited的flag
: 简单说这题就是find in-order traverse next node
: or find next big in BST
l*a
24 楼
真的吗？
stack其实就是recursion.难道recursion里会重复调用同一个结点？
我明天写写看看，你业可以拿出来证据
【在 h****e 的大作中提到】
: 没有visited flag的话，同一个结点可能反复压栈。peking2的code
: 用了HashSet也是一样的道理。
stack其实就是recursion.难道recursion里会重复调用同一个结点？
我明天写写看看，你业可以拿出来证据
【在 h****e 的大作中提到】
: 没有visited flag的话，同一个结点可能反复压栈。peking2的code
: 用了HashSet
p*2
25 楼
我觉得每一个node有两个状态。如果recursion, 调left之前一个状态，调left之后一
个状态。visited就是来模拟这个状态。
【在 l*****a 的大作中提到】
: 真的吗？
: stack其实就是recursion.难道recursion里会重复调用同一个结点？
: 我明天写写看看，你业可以拿出来证据
g*e
26 楼
iterative inorder traversal without visited flag
void in_order_traversal_iterative(BinaryTree *root) {
stack s;
BinaryTree *current = root;
while (!s.empty() || current) {
if (current) {
s.push(current);
current = current->left;
} else {
current = s.top();
s.pop();
cout << current->data << " ";
current = current->right;
}
}
}
void in_order_traversal_iterative(BinaryTree *root) {
stack
BinaryTree *current = root;
while (!s.empty() || current) {
if (current) {
s.push(current);
current = current->left;
} else {
current = s.top();
s.pop();
cout << current->data << " ";
current = current->right;
}
}
}
z*8
27 楼
呵呵， leetcode大神那边拿来的吧
【在 g*********e 的大作中提到】
: iterative inorder traversal without visited flag
: void in_order_traversal_iterative(BinaryTree *root) {
: stack s;
: BinaryTree *current = root;
: while (!s.empty() || current) {
: if (current) {
: s.push(current);
: current = current->left;
: } else {
: current = s.top();
【在 g*********e 的大作中提到】
: iterative inorder traversal without visited flag
: void in_order_traversal_iterative(BinaryTree *root) {
: stack
: BinaryTree *current = root;
: while (!s.empty() || current) {
: if (current) {
: s.push(current);
: current = current->left;
: } else {
: current = s.top();
g*e
28 楼
应该是的
p*2
29 楼
这么写还挺容易出错的。
【在 g*********e 的大作中提到】
: iterative inorder traversal without visited flag
: void in_order_traversal_iterative(BinaryTree *root) {
: stack
: BinaryTree *current = root;
: while (!s.empty() || current) {
: if (current) {
: s.push(current);
: current = current->left;
: } else {
: current = s.top();
h*e
30 楼
明白了。我原先的想法是遍历的时候as lazy as possible，只要一找到
合适的结点就立刻返回。这样增加了程序的复杂度，造成有的结点多次入栈
和出栈，虽然两种方法入栈和出栈操作的次数似乎都是一样的。
下面是改写后的程序以及一个实例做比较：
class BinaryTreeIterator {
Stack stack = new Stack();
public BinaryTreeIterator(Node root) {
while (root!=null) {
stack.push(root);
root = root.left;
}
}
public boolean hasNext() {
return !stack.empty();
}
public Node next() {
Node node = stack.pop();
Node current = node.right;
while (current!=null) {
stack.push(current);
current = current.left;
}
return node;
}
}
5
/ \
1 8
\ /
3 6
\
4
最初的方法：
IN: 5 8 5 3 4 8
OUT: 5 3 4 5 8 8
PRINT: 1 3 4 5 6 8
改进后的方法：
IN: 5 1 3 4 8 6
OUT: 1 3 4 5 6 8
PRINT: 1 3 4 5 6 8
合适的结点就立刻返回。这样增加了程序的复杂度，造成有的结点多次入栈
和出栈，虽然两种方法入栈和出栈操作的次数似乎都是一样的。
下面是改写后的程序以及一个实例做比较：
class BinaryTreeIterator {
Stack
public BinaryTreeIterator(Node root) {
while (root!=null) {
stack.push(root);
root = root.left;
}
}
public boolean hasNext() {
return !stack.empty();
}
public Node next() {
Node node = stack.pop();
Node current = node.right;
while (current!=null) {
stack.push(current);
current = current.left;
}
return node;
}
}
5
/ \
1 8
\ /
3 6
\
4
最初的方法：
IN: 5 8 5 3 4 8
OUT: 5 3 4 5 8 8
PRINT: 1 3 4 5 6 8
改进后的方法：
IN: 5 1 3 4 8 6
OUT: 1 3 4 5 6 8
PRINT: 1 3 4 5 6 8
G*s
31 楼
一般面试最好写那个带FLAG版本的，不容出错；
不用FLAG版本的如下,c++版你可以写个类似这个->
void iterativeInorder(Node* root) {
stack nodeStack;
Node *curr = root;
while (true) {
if (curr) {
nodeStack.push(curr);
curr = curr->left;
continue;
}
if (!nodeStack.size()) {
return;
}
curr = nodeStack.top();
nodeStack.pop();
std::cout << "Node data: " << curr->data << std::endl;
curr = curr->right;
}
}
I
【在 z*********8 的大作中提到】
: 我估计不能在内部存一个stack吧， 是不是可以加个parent pointer？如果不能改，怎
: 么做？
不用FLAG版本的如下,c++版你可以写个类似这个->
void iterativeInorder(Node* root) {
stack
Node *curr = root;
while (true) {
if (curr) {
nodeStack.push(curr);
curr = curr->left;
continue;
}
if (!nodeStack.size()) {
return;
}
curr = nodeStack.top();
nodeStack.pop();
std::cout << "Node data: " << curr->data << std::endl;
curr = curr->right;
}
}
I
【在 z*********8 的大作中提到】
: 我估计不能在内部存一个stack吧， 是不是可以加个parent pointer？如果不能改，怎
: 么做？
q*c
32 楼
你这个不是iterator， 而是traversal, 两个是不一样的.Iterator class 要有一个
current state 指向 current node, 每次执行 advance/++ (C++) 或者next(Java)操
作，返回下一个node. 所以inorder iterator 实际上就是找到下一个inorder node.
current state 指向 current node, 每次执行 advance/++ (C++) 或者next(Java)操
作，返回下一个node. 所以inorder iterator 实际上就是找到下一个inorder node.
p*2
33 楼
意思差不多。有了traversal，iterator就不难写。
【在 q********c 的大作中提到】
: 你这个不是iterator， 而是traversal, 两个是不一样的.Iterator class 要有一个
: current state 指向 current node, 每次执行 advance/++ (C++) 或者next(Java)操
: 作，返回下一个node. 所以inorder iterator 实际上就是找到下一个inorder node.
j*u
34 楼
把traversal 里面的while循环 改成 if 意思就差不多了,既然每次是in-order遍历出
一个点。
一个点。
w*x
35 楼
这题作的不下5遍了, 说实话, 第一次做还挺不容易的:
============带parent===========================
void InOrderPrint(NODE* pRoot)
{
assert(pRoot);
NODE* pCur = pRoot;
while (pCur != NULL)
{
while (pCur->pLft != NULL)
{
cout<nVal<
}
cout<nVal<
while (pCur != NULL)//use "pCur != NULL" rather than "pCur->pParent
!= NULL"
{
//Don't miss "pCur->pParent != NULL" logic
if (pCur->pParent != NULL && pCur != pCur->pParent->pRgt)
{
pCur = pCur->pParent->pRgt;
break;
}
pCur = pCur->pParent;
}
}
}
==================== use stack ====================================
void _left_push2(NODE* pNode, stack& stk)
{
assert(pNode);
while (pNode != NULL)
{
stk.push(pNode);
pNode = pNode->pLft;
}
}
void InOrderPrint(NODE* pRoot)
{
assert(pRoot);
stack stk;
_left_push2(pRoot, stk);
while (!stk.empty())
{
NODE* pTop = stk.top();
assert(pTop);
stk.pop();
cout<nVal<
_left_push2(pTop->pRgt, stk);
}
}
============带parent===========================
void InOrderPrint(NODE* pRoot)
{
assert(pRoot);
NODE* pCur = pRoot;
while (pCur != NULL)
{
while (pCur->pLft != NULL)
{
cout<
}
cout<
while (pCur != NULL)//use "pCur != NULL" rather than "pCur->pParent
!= NULL"
{
//Don't miss "pCur->pParent != NULL" logic
if (pCur->pParent != NULL && pCur != pCur->pParent->pRgt)
{
pCur = pCur->pParent->pRgt;
break;
}
pCur = pCur->pParent;
}
}
}
==================== use stack ====================================
void _left_push2(NODE* pNode, stack
{
assert(pNode);
while (pNode != NULL)
{
stk.push(pNode);
pNode = pNode->pLft;
}
}
void InOrderPrint(NODE* pRoot)
{
assert(pRoot);
stack
_left_push2(pRoot, stk);
while (!stk.empty())
{
NODE* pTop = stk.top();
assert(pTop);
stk.pop();
cout<
_left_push2(pTop->pRgt, stk);
}
}
相关阅读
论7万买54万房贷款30万没有garbage disposal有没有问题ZT:美国买房详细流程冰箱问题请教：冷冻室关门会有奇怪的冲水还是充气的声音patio的砖缝长草，能用round up么？也问木工大牛们：Miter Saw的选择这个Condo能买吗Ikea的家具，没啥甲醛味儿啊，应该没有毒吧无娃，可撑买个大房子，就是无年轻人的无忧的生活了...有经济实用型洗衣机推荐吗？DIYer们，说说你们出过的是故把？老中在美国，就像中世纪的犹太人Spring TX 5小孩1大人被relative枪杀 (转载)推荐HDTV老中相信实木、砖头、水泥板离墓地的距离买房纠结，这样算不算撑？问问木头大牛们，郭美美与郭伯雄是一家么？你们炒菜还放味精吗？老毛病又犯了，老张有啥妙招吗？