Let
struct treeNode{
int id;
treeNode *left;
treeNode *right;
treeNode *par;
};

DFS(treeNode *root){
treeNode *cur=root;
while (cur!=NULL){
printf("%d, ", cur->id);
if (cur->left!=NULL){
cur=cur->left;
}
else if (cur->right!=NULL)
cur=cur->right;
else{
treeNode *par=cur->par;
while (par!=NULL){
if (par->left==cur && par->right!=NULL){
cur=par->right;
break;
}
cur=par;
par=par->par;
}
if (par==NULL) cur=NULL;
}
}
}

其实就是depth first, 应该是O(3n)=O(n)吧。