二叉树的非递归遍历

1. 先序遍历的非递归实现

 1 vector<int> pre_order(TreeNode* root){
 2     vector<int> res;
 3     stack<TreeNode* > st;
 4     if(root!=NULL) st.push(root);
 5     while(!st.empty()){
 6         TreeNode* node = st.top();
 7         st.pop();
 8         res.push_back(node->val);
 9         if(node->right != NULL) st.push(node->right);
10         if(node->left != NULL) st.push(node->left);
11     }
12     return res;
13 }

2. 中序遍历的非递归实现

 1 vector<int> in_order(TreeNode* root){
 2     vector<int> res;
 3     stack<TreeNode*> st;
 4     if(root != NULL) st.push(root);
 5     TreeNode* cur =root;
 6     while(!st.empty()){
 7         // 如果cur为空，弹出栈顶元素，并将cur设置为弹出节点的右孩子
 8         if(cur == NULL){
 9             res.push_back(st.top()->val);
10             cur = st.top()->right;
11             st.pop();
12         }else        // 否则继续找左孩子
13             cur = cur->left;
14         if(cur != NULL)
15             st.push(cur);
16     }
17     return res;
18 }

3. 后序遍历的非递归实现

// 后序遍历的非递归实现(双栈实现)
vector<int> post_order(TreeNode* root){
    vector<int> res;
    stack<TreeNode*> s1;
    stack<int> s2;
    if(root!=NULL) s1.push(root);
    while(!s1.empty()){
        TreeNode* node = s1.top();
        s1.pop();
        s2.push(node->val);
        if(node->left != NULL) s1.push(node->left);
        if(node->right != NULL) s1.push(node->right);
    }
    while(!s2.empty()){
        res.push_back(s2.top());
        s2.pop();
    }
    return res;
}

 1 // 后序遍历的非递归实现（单个栈实现）
 2 vector<int> post_order_2(TreeNode* root){
 3     vector<int> res;
 4     stack<TreeNode*> st;
 5     TreeNode* last = root, *cur = NULL;
 6     if(root != NULL) st.push(root);
 7     while(!st.empty()){
 8         cur = st.top();
 9         // 如果左子树没遍历结束
10         if(cur->left!=NULL && last!=cur->left && last!=cur->right)
11             st.push(cur->left);
12         else if(cur->right!=NULL && last!=cur->right)
13             st.push(cur->right);
14         else{
15             last = cur;
16             res.push_back(st.top()->val);
17             st.pop();
18         }
19     }
20     return res;
21 }