0、 Preface

This blog is to buckle 145. Postorder traversal of binary trees Problem solving , The title is simple. , Blogging is mainly because it can also be used as DFS Examples ~

Preorder traversal of binary tree Click here to To view the ！
The middle order traversal of binary tree can Click here to To view the ！

1、 Title Description

2、 Their thinking

2.1 Method 1 ~ recursive

2.1.1 Ideas

The post order traversal of binary tree is based on the access The left subtree – Right subtree – The root node Traverse the target tree in a way , When accessing the left subtree or right subtree, you can traverse in the same way , Until you walk through the whole tree . In combination with this approach, recursion can be used directly ！

2.1.2 Program code

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */
class Solution {
    
public:
    void postorder(TreeNode* root, vector<int>& ans)
    {
    
        if(!root)
            return;
        postorder(root->left,ans);
        postorder(root->right,ans);
        ans.push_back(root->val);
    }
    vector<int> postorderTraversal(TreeNode* root) {
    
        vector<int> ans;
        postorder(root,ans);
        return ans;
    }
};

2.2 Method 2 ~ DFS

2.2.1 Ideas

What about this idea , Is based on the force given on the buckle DFS Templates 2 Written by . Although it feels more like iteration , harm ！

The idea here is equivalent to the method 1 The train of thought unfolds , From implicit stack to explicit stack , Everything else is the same , The specific implementation can be seen in the following code . But when expanding here, you need to judge the right subtree ！ See the following procedure for details

2.2.2 Program code

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */
class Solution {
    
public:
    vector<int> postorderTraversal(TreeNode* root) {
    
        vector<int> ans;
        stack<TreeNode*> st;
        TreeNode* cur = root;
        TreeNode* prev;
        while(cur || !st.empty())
        {
    
            while(cur)
            {
    
                st.push(cur);
                cur = cur->left;
            }
            TreeNode* top = st.top();
            if(top->right == nullptr || top->right == prev)
            {
    
                ans.push_back(top->val);
                st.pop();
                prev = top;
            }
            else
                cur = top->right;
        }
        return ans;
    }
};