二叉树的非递归前中后序遍历

非递归的思路。

个人感觉这句话很有用。

本质上是在模拟递归,因为在递归的过程中使用了系统栈,所以在迭代的解法中常用Stack来模拟系统栈。

中序遍历

左根右,在递归的时候,如果当前节点有左子树,我们就递归左子树,然后输出中间节点,然后递归右子树。
我们用stack模拟这个操作。

使用cur来调度当前的节点,而不是仅用stack。

 vector<int> inorderTraversal(TreeNode* root) {
        if(!root) return {};
        stack<TreeNode *> st;
        TreeNode* cur = root;

        vector<int>ans;
        while(!st.empty() || cur){
            while(cur){
                st.push(cur);
                cur = cur->left;
            }
            TreeNode* now  = st.top();st.pop();
            ans.push_back(now->val);
            if(now->right){
                cur = now->right;
            }
        }
        return ans;

    }

前序遍历

根左右。 可以方便的使用注释中给出的实现。为了统一三种非递归遍历的写法,这里仍然采用 cur来调度。


vector<int> preorderTraversal(TreeNode* root) { // 迭代版。用stack, // vector<int>ans; // stack<TreeNode*>st; // if(root!= NULL) st.push(root); // while(!st.empty()){ // TreeNode* top = st.top();st.pop(); // ans.push_back(top->val); // if(top->right) st.push(top->right); // if(top->left) st.push(top->left); // } vector<int>ans; stack<TreeNode*>st; TreeNode* cur = root; while(!st.empty() || cur){ while(cur){ ans.push_back(cur->val); st.push(cur); cur=cur->left; } TreeNode* now = st.top();st.pop(); if(now->right){ cur = now->right; } } return ans; }

后序遍历

后序遍历由前序遍历更改而来。 前序遍历是 根左右。 后序遍历是 左右根 = reverse(根右左)。


vector<int> postorderTraversal(TreeNode* root) { vector<int>ans; TreeNode* cur = root; //后序遍历由前序遍历更改而来。 前序遍历是 根左右。 后序遍历是 左右根 = reverse(根右左)。 stack<TreeNode*> st; while(!st.empty() || cur){ while(cur){ ans.push_back(cur->val); st.push(cur); cur = cur->right; // 先右 } TreeNode* now = st.top();st.pop(); if (now->left) cur = now->left; // 后左 } reverse(ans.begin(), ans.end()); return ans; }

参考链接

https://leetcode-cn.com/problems/binary-tree-postorder-traversal/solution/er-cha-shu-hou-xu-fei-di-gui-bian-li-liang-chong-z/

点赞