z*********8
发帖数: 2070 | 1 我估计不能在内部存一个stack吧， 是不是可以加个parent pointer？如果不能改，怎
么做？ |
l*****a
发帖数: 14598 | 2 为什么内部不能存一个stack?
【在 z*********8 的大作中提到】
: 我估计不能在内部存一个stack吧， 是不是可以加个parent pointer？如果不能改，怎
: 么做？
|
z*********8
发帖数: 2070 | 3 请问怎么做？
我想的作弊方法就是在constructor里面直接inorder recursion走一遍把所有node存到
stack里面。。。
【在 l*****a 的大作中提到】
: 为什么内部不能存一个stack?
|
l*****a
发帖数: 14598 | 4 你全存进去有点过分了。
不能只存部分吗？然后每步HasNext()用find next node for in-order traverse
实现不可以吗
【在 z*********8 的大作中提到】
: 请问怎么做？
: 我想的作弊方法就是在constructor里面直接inorder recursion走一遍把所有node存到
: stack里面。。。
|
g*********e
发帖数: 14401 | |
z*********8
发帖数: 2070 | 6 我直接应该这么做， 但是不会写啊
求代码！
【在 l*****a 的大作中提到】
: 你全存进去有点过分了。
: 不能只存部分吗？然后每步HasNext()用find next node for in-order traverse
: 实现不可以吗
|
l*****a
发帖数: 14598 | 7 有MSFT L61 offer的这都不会写？
sde OR sdet?
【在 z*********8 的大作中提到】
: 我直接应该这么做， 但是不会写啊
: 求代码！
|
z*********8
发帖数: 2070 | 8 janitor
【在 l*****a 的大作中提到】
: 有MSFT L61 offer的这都不会写？
: sde OR sdet?
|
p*****2
发帖数: 21240 | 9 好多简单题也没练过。赶紧写一个练练。
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;
}
} |
z*********8
发帖数: 2070 | 10 我已经知道怎么写了， 不过你这个。。。
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
发帖数: 21240 | 11
啥意思？跟iterator什么关系？
【在 z*********8 的大作中提到】
: 我已经知道怎么写了， 不过你这个。。。
: iterator应该提供hasNext和Next吧
|
l*****a
发帖数: 14598 | 12 天资聪颖的JANITOR
这么快就会了
【在 z*********8 的大作中提到】
: 我已经知道怎么写了， 不过你这个。。。
: iterator应该提供hasNext和Next吧
|
z*********8
发帖数: 2070 | |
p*****2
发帖数: 21240 | |
z*********8
发帖数: 2070 | 15 意思是每次调用next， 打印出来的节点顺序应该和inorder traversal一样
【在 p*****2 的大作中提到】
:
: 跟这道题又什么关系呢？
|
p*****2
发帖数: 21240 | 16
明白了。没看清除题目。
【在 z*********8 的大作中提到】
: 意思是每次调用next， 打印出来的节点顺序应该和inorder traversal一样
|
b********e
发帖数: 386 | 17 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？如果不能改，怎
: 么做？
|
h****e
发帖数: 928 | 18 这道题看起来简单，用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);
}
} |
l*****a
发帖数: 14598 | 19 没细看，但是想不出来为什么要有个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;
: }
: }
|
p*****2
发帖数: 21240 | 20
我也用了visited, 不过这题我以前没做过，不一定是最优。
【在 l*****a 的大作中提到】
: 没细看，但是想不出来为什么要有个visited的flag
: 简单说这题就是find in-order traverse next node
: or find next big in BST
|
|
|
h****e
发帖数: 928 | 21 没有visited flag的话，同一个结点可能反复压栈。peking2的code
用了HashSet也是一样的道理。
【在 l*****a 的大作中提到】
: 没细看，但是想不出来为什么要有个visited的flag
: 简单说这题就是find in-order traverse next node
: or find next big in BST
|
l*****a
发帖数: 14598 | 22 真的吗？
stack其实就是recursion.难道recursion里会重复调用同一个结点？
我明天写写看看，你业可以拿出来证据
【在 h****e 的大作中提到】
: 没有visited flag的话，同一个结点可能反复压栈。peking2的code
: 用了HashSet也是一样的道理。
|
p*****2
发帖数: 21240 | 23
我觉得每一个node有两个状态。如果recursion, 调left之前一个状态，调left之后一
个状态。visited就是来模拟这个状态。
【在 l*****a 的大作中提到】
: 真的吗？
: stack其实就是recursion.难道recursion里会重复调用同一个结点？
: 我明天写写看看，你业可以拿出来证据
|
g*********e
发帖数: 14401 | 24 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;
}
}
} |
z*********8
发帖数: 2070 | 25 呵呵， 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
发帖数: 14401 | |
p*****2
发帖数: 21240 | 27
这么写还挺容易出错的。
【在 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();
|
h****e
发帖数: 928 | 28 明白了。我原先的想法是遍历的时候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 |
G**********s
发帖数: 70 | 29 一般面试最好写那个带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？如果不能改，怎
: 么做？
|
q********c
发帖数: 1774 | 30 你这个不是iterator， 而是traversal, 两个是不一样的.Iterator class 要有一个
current state 指向 current node, 每次执行 advance/++ (C++) 或者next(Java)操
作，返回下一个node. 所以inorder iterator 实际上就是找到下一个inorder node. |
|
|
p*****2
发帖数: 21240 | 31
意思差不多。有了traversal，iterator就不难写。
【在 q********c 的大作中提到】
: 你这个不是iterator， 而是traversal, 两个是不一样的.Iterator class 要有一个
: current state 指向 current node, 每次执行 advance/++ (C++) 或者next(Java)操
: 作，返回下一个node. 所以inorder iterator 实际上就是找到下一个inorder node.
|
j***u
发帖数: 16 | 32 把traversal 里面的while循环 改成 if 意思就差不多了,既然每次是in-order遍历出
一个点。 |
w****x
发帖数: 2483 | 33 这题作的不下5遍了, 说实话, 第一次做还挺不容易的:
============带parent===========================
void InOrderPrint(NODE* pRoot)
{
assert(pRoot);
NODE* pCur = pRoot;
while (pCur != NULL)
{
while (pCur->pLft != NULL)
{
cout<nVal<
pCur = pCur->pLft;
}
cout<nVal<
//The ending condition is tricky but simple
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<
if (pTop->pRgt != NULL)
_left_push2(pTop->pRgt, stk);
}
} |
