s******d 发帖数: 61 | 1 Iterative way ofr single preorderTraversal
public void preorderTraversal(Node root){
Stack stack=new Stack();
stack.push(root);
while(true){
Node current=stack.pop();
if(current==null) break;
Node right=current.getRight();
if(right!=null)
stack.push(right);
Node left=current.getLeft();
if(left!=null)
stack.push(left);
}
}
这个是preorderTraversal, 这样怎么转成inorder呢? |
s******d 发帖数: 61 | |
e*****3 发帖数: 610 | 3 以前见过这种pushLeft的帮法,你可以调试一下。
public void inorderTraverse(Node root) {
Stack s = new Stack();
pushLeft(root, s);
while (s.size() > 0) {
Node node = s.pop();
print(node); // Visit the current node
pushLeft(node.right, s); // Visit the right subtree
}
}
private void pushLeft(Node node, Stack stack) {
while (node != null) {
stack.push(node);
node = node.left;
}
}
【在 s******d 的大作中提到】 : 还是没想出来啊
|
s******d 发帖数: 61 | |
d*******d 发帖数: 2050 | 5 in c:
void inorder(Node * root){
stack mystack;
Node * p = root;
while( !mystack.empty() || p != 0 ){
if( p ){
mystack.push(p);
p = p->left;
}else{
p = mystack.top();
mystack.pop();
// do something to p;
p = p->right;
}
}
}
【在 s******d 的大作中提到】 : Iterative way ofr single preorderTraversal : public void preorderTraversal(Node root){ : Stack stack=new Stack(); : stack.push(root); : while(true){ : Node current=stack.pop(); : if(current==null) break; : Node right=current.getRight(); : if(right!=null) : stack.push(right);
|