手写非递归遍历二叉树、前序、中序、后序

「爱情、让人受尽委屈。」 2021-12-23 23:09 313阅读 0赞

### 非递归遍历二叉树 ###

*   *  前序
     *  中序
     *  后序

## 前序 ##

1、利用一个栈，先把根节点放进去
    2、直接取出来，栈顶节点进行操作
    3、如果栈顶节点的右子树存在的话，入栈
    4、如果栈顶节点的左子树存在的话，入栈
    5、重复2、3、4步骤

参考代码

vector<int> preorderTraversal(TreeNode* root) { 
            vector<int>output;
            if(root == nullptr) return output;
            stack<TreeNode*>s;
            s.push(root);
            while(!s.empty()){ 
                TreeNode* node = s.top();
                s.pop();
                output.push_back(node->val);
                if(node->right) s.push(node->right);
                if(node ->left)  s.push(node->left);
            }
            return output;
        }

## 中序 ##

非递归思路

1、利用一个栈结构作为辅助空间
    2、首要递归遍历左节点并入栈，直到为空
    3、取出栈顶元素，然后进行相应操作
    4、递归遍历右子树的元素
    5、重复2、3、4步骤

参考代码

vector<int> inorderTraversal(TreeNode* root) { 
            vector<int>output;
            stack<TreeNode*>s;
            while(!s.empty() || root != nullptr){ 
                while(root){ 
                    s.push(root);
                    root = root->left;  
                }
                root = s.top();
                output.push_back(root->val);
                s.pop();
                root = root->right;
            }
            return output;
        }

## 后序 ##

非递归实现思路

步骤1、转换思路，后序遍历的顺序是左，右，中，可以按照中、右、左遍历好，然后逆序
    步骤2、把根节点放进栈容器中，先遍历根节点
    步骤3、如果右节点存在的话，入栈
    步骤4、如果左节点存在的话，入栈
    步骤5、重复上述2、3、4步骤
    步骤6、把遍历好的数据进行逆序

参考代码

vector<int> postorderTraversal(TreeNode* root) { 
            vector<int>output;
            if(root == nullptr) return output;
            stack<TreeNode*>s;
            s.push(root);
            while(!s.empty()){ 
                TreeNode* node = s.top();
                s.pop();
                output.push_back(node->val);
                if(node->left) s.push(node->left);
                if(node->right) s.push(node->right);
            }
            reverse(output.begin(),output.end());
            return output;
        }