中序遍历

也叫中根序遍历，也就是“左根中”

递归

void midOrderTraversal(TreeNode* root) {
    if(!root)    return;
    midOrderTraversal(root->left);
    visit(root);
    midOrderTraversal(root->right);
}

非递归

void midOrderTraversal(TreeNode* root) {
    stack<TreeNode*> stk;
    TreeNode* p = root;
    while(!stk.empty() || p) {
        while(p){
            stk.push(p);
            p = p->left;
        }
        if(!stk.empty()){
             p = s.top();
            s.pop();
            visit(p);
            p = p->right;
        }
    }
}

先（前）序遍历

递归

void preOrderTraversal(TreeNode* root) {
    if(!root)    return;
    visit(root);
    midOrderTraversal(root->left);
    midOrderTraversal(root->right);
}

非递归

void midOrderTraversal(TreeNode* root) {
    stack<TreeNode*> stk;
    TreeNode* p = root;
    while(!stk.empty() || p) {
        while(p){
            stk.push(p);
            visit(p);
            p = p->left;
        }
        if(!stk.empty()){
             p = s.top();
            s.pop();
            p = p->right;
        }
    }
}

后序遍历

递归

void postOrderTraversal(TreeNode* root) {
    if(!root)    return;
    midOrderTraversal(root->left);
    midOrderTraversal(root->right);
    visit(root);
}

非递归

void postOrderTraversal(TreeNode* root) {
    stack<TreeNode*> stk;
    TreeNode* pre = NULL;
    while(!stk.empty() || root) {
        while(root){
            stk.push(root);
            root = root->left;
        }
        root = stk.top();
        stk.pop();
        if(!root->right || root->right == pre) {
            visit(root);
            pre = root;
            root = NULL;
        }
        else{
            stk.push(root);
            root = root->right;
        }
    }
}