0、 Preface

This blog is to buckle 144. Preorder traversal of two tree Problem solving , The title is simple. , Blogging is mainly because it can also be used as DFS Examples ~

And this blog is actually related to Writing to remember ~ Middle order traversal of binary trees The implementation of middle order traversal in is almost , Can compare memory ~

The middle order traversal of binary tree can Click here to To view the ！
The post 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 preorder traversal of a binary tree is based on access The root node – The left subtree – Right subtree 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 preorder(TreeNode* root,vector<int>& ans)
    {
    
        if(!root)
            return;
        ans.push_back(root->val);
        preorder(root->left,ans);
        preorder(root->right,ans);
    }
    vector<int> preorderTraversal(TreeNode* root) {
    
        vector<int> ans;
        preorder(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 .

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> preorderTraversal(TreeNode* root) {
    
        vector<int> ans;
        TreeNode* cur = root;
        stack<TreeNode*> st;
        while(cur || !st.empty())
        {
    
            while(cur)
            {
    
                st.push(cur);
                ans.push_back(cur->val);
                cur = cur->left;
            }
            cur = st.top();
            st.pop();
            cur=cur->right;
        }
        return ans;
    }
};