二叉树的遍历

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
/ 
 /**递归算法**/
void PreOrder(TreeNode* root){
    if(!root)
        return;
    cout << root->val;
    PreOrder(root->left);
    PreOrder(root->right);
}

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

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

/**非递归算法**/
void PreOrder(TreeNode* root){
    if(!root)
        return;
    stack<TreeNode*> st;
    TreeNode *p = root;
    while(p || !st.empty()){
        while(p){
            st.push(p);
            cout << p->val;
            p = p->left;
        }
        if(!st.empty()){
            p = st.top();
            stack.pop();
            p = p->right;
        }
    }
}

void InOrder(TreeNode* root){
    if(!root)
        return;
    stack<TreeNode*> st;
    TreeNode *p = root;
    while(p || !st.empty){
        while(p){
            st.push(p);
            p = p->left;
        }
        if(!st.empty()){
            p = st.top();
            cout << p->val;
            p = p->right;
        }
    }
}

void PostOrder(TreeNode* root){
    if(!root)
        return;
    stack<TreeNode*> st;
    TreeNode *cur, *pre = NULL;
    st.push(root);
    while(!st.empty()){
        cur = st.top();
        if( (!cur->left && !cur->right) || (!pre && (cur->left == pre || cur->right == pre) ) ){
            cout << cur->val;
            st.pop();
            pre = cur;
        }
        else{
            if(cur->right)
                st.push(cur->right);
            if(cur->left)
                st.push(cur->left);
        }
    }
}

/*广度优先遍历*/
void bfs(TreeNode* root){
    if(!root)
        return;
    queue<TreeNode*> q;
    q.push(root);
    while(!q.empty()){
        TreeNode *temp = q.front();
        q.pop();
        cout << temp->val;
        if(temp->left)
            q.push(temp->left);
        if(temp->right)
            q.push(temp->right);
    }
}