BST Traversal

本文包含二叉搜索树的遍历，包括前序遍历、中序遍历、后序遍历的递归和非递归实现。

但是没有什么好讲解的，就是熟练掌握递归和非递归的写法，以及非递归的后序遍历的写法。

Recursive #

Preorder Traversal #


void dfs(TreeNode* root){
    if(!root)return;
    cout<<root->val<<endl;
    dfs(root->left);
    dfs(root->right);
}

Inorder Traversal #

void dfs(TreeNode* root){
    if(!root)return;
    dfs(root->left);
    cout<<root->val<<endl;
    dfs(root->right);
}

Postorder Traversal #

void dfs(TreeNode* root){
    if(!root)return;
    dfs(root->left);
    dfs(root->right);
    cout<<root->val<<endl;
}

Iterative #

Preorder Traversal #

void pre_order(TreeNode* root){
    TreeNode* cur = root;
    stack<TreeNode*> stk;
    while(cur||stk.size()){
        while(cur){
            cout<<cur->val<<endl;
            stk.push(cur);
            cur = cur->left;
        }
        cur = stk.top()->right;
        stk.pop();
    }
}

Inorder Traversal #

void in_order(TreeNode* root){
    TreeNode* cur = root;
    stack<TreeNode*> stk;
    while(cur||stk.size()){
        while(cur){
            stk.push(cur);
            cur = cur->left;
        }
        cout<<stk.top()->val<<endl;
        cur = stk.top()->right;
        stk.pop();
    }
}

Postorder Traversal #

void post_order(TreeNode* root){
    TreeNode* cur = root;
    stack<TreeNode*> stk;
    TreeNode* pre = nullptr;
    while(cur||stk.size()){
        while(cur){
            stk.push(cur);
            cur = cur->left;
        }
        cur = stk.top();
        if(cur->right==nullptr||cur->right==pre){
            cout<<cur->val<<endl;
            pre = cur;
            stk.pop();
            cur = nullptr;
        }else{
            cur = cur->right;
        }
    }
}