[daily question 1] traversal of binary tree

Recursive traversal

Here to help you identify the three elements of recursive algorithm . Every time you write recursion , Write according to these three elements , Can ensure that you write the correct recursive algorithm ！

1. Determine the parameters and return values of recursive functions ： Determine which parameters need to be processed in the recursive process , Then add this parameter to the recursive function , What is the return value of each recursion, and then determine the return type of recursive function .
2. Determine termination conditions ： The recursive algorithm is finished , When it's running , We often encounter stack overflow errors , The termination condition is not written or the termination condition is not written correctly , The operating system also uses a stack structure to store the recursive information of each layer , If recursion doesn't stop , The memory stack of the operating system is bound to overflow .
3. Determine the logic of monolayer recursion ： Determine what information each level of recursion needs to process . In this case, you will repeatedly call yourself to realize the recursive process .

The former sequence traversal

class Solution {
    
public:
    void traversal(TreeNode* cur, vector<int>& vec) {
    
        if (cur == NULL) return;
        vec.push_back(cur->val);    //  in 
        traversal(cur->left, vec);  //  Left 
        traversal(cur->right, vec); //  Right 
    }
    vector<int> preorderTraversal(TreeNode* root) {
    
        vector<int> result;
        traversal(root, result);
        return result;
    }
};

In the sequence traversal

class Solution {
    
public:
    void traversal(TreeNode* cur, vector<int>& vec) {
    
         if (cur == NULL) return;
	     traversal(cur->left, vec);  //  Left 
	     vec.push_back(cur->val);    //  in 
	     traversal(cur->right, vec); //  Right 
    }
    vector<int> postorderTraversal(TreeNode* root) {
    
        vector<int> result;
        traversal(root, result);
        return result;
    }
};

After the sequence traversal

class Solution {
    
public:
    void traversal(TreeNode* cur, vector<int>& vec) {
    
         if (cur == NULL) return;
   		 traversal(cur->left, vec);  //  Left 
  	     traversal(cur->right, vec); //  Right 
         vec.push_back(cur->val);    //  in 
    }
    vector<int> postorderTraversal(TreeNode* root) {
    
        vector<int> result;
        traversal(root, result);
        return result;
    }
};

Sequence traversal

class Solution {
    
public:
    void order(TreeNode* cur, vector<vector<int>>& result, int depth)
    {
    
        if (cur == nullptr) return;
        if (result.size() == depth) result.push_back(vector<int>());
        result[depth].push_back(cur->val);
        order(cur->left, result, depth + 1);
        order(cur->right, result, depth + 1);
    }
    vector<vector<int>> levelOrder(TreeNode* root) {
    
        vector<vector<int>> result;
        int depth = 0;
        order(root, result, depth);
        return result;
    }
};

Iterate through

The implementation of recursion is ： Every recursive call takes the local variable of the function 、 Parameter values and return addresses are pushed into the call stack , And then when recursion returns , Pop up the parameters of the last recursion from the top of the stack , So that's why recursion can return to the next level .

At this point, you should know that we can also use the stack to realize the traversal of the binary tree in the order before and after .

The former sequence traversal （ iteration ）

The forward order traversal is about the middle , Each time, the intermediate node is processed first , Then put the root node on the stack first , Then add the right child to the stack , Add the left child .

lass Solution {
    
public:
    vector<int> preorderTraversal(TreeNode* root) {
    
        stack<TreeNode*> st;
        vector<int> result;
        if (root == NULL) return result;
        st.push(root);
        while (!st.empty()) {
    
            TreeNode* node = st.top();                     //  in 
            st.pop();
            result.push_back(node->val);
            if (node->right) st.push(node->right);         //  Right （ Empty nodes do not stack ）
            if (node->left) st.push(node->left);           //  Left （ Empty nodes do not stack ）
        }
        return result;
    }

In the sequence traversal

The middle order traversal is left, middle and right , The node at the top of the binary tree is accessed first , Then, layer by layer, access down , Until you reach the bottom of the tree to the left , And then we start processing nodes （ That is, put the node value in result Array ）, This leads to the inconsistency between the processing order and the access order .

that In using iteration method to write order traversal , To access the pointer, you need help , Stacks are used to handle elements on nodes .

class Solution {
    
public:
    vector<int> inorderTraversal(TreeNode* root) {
    
        vector<int> result;
        stack<TreeNode*> st;
        TreeNode* cur = root;
        while (cur != NULL || !st.empty()) {
    
            if (cur != NULL) {
     //  Pointer to access the node , Access to the bottom 
                st.push(cur); //  Put the visited node on the stack 
                cur = cur->left;                //  Left 
            } else {
    
                cur = st.top();
                 //  Data that pops up from the stack , Is the data to be processed （ In the result The data in the array ）
                st.pop();
                result.push_back(cur->val);     //  in 
                cur = cur->right;               //  Right 
            }
        }
        return result;
    }
};

After the sequence traversal

Let's look at postorder traversal , First order traversal is about middle , The subsequent traversal is left and right , So we just need to adjust the code order of preorder traversal , It becomes the middle right left traversal order , And then in reverse result Array , The order of output results is left and right , Here's the picture ：

So the post order traversal only needs a little modification of the code of the previous traversal , The code is as follows ：

class Solution {
    
public:
    vector<int> postorderTraversal(TreeNode* root) {
    
        stack<TreeNode*> st;
        vector<int> result;
        if (root == NULL) return result;
        st.push(root);
        while (!st.empty()) {
    
            TreeNode* node = st.top();
            st.pop();
            result.push_back(node->val);
            if (node->left) st.push(node->left); 
            //  Relative to preorder traversal , This changes the order of stack entry  （ Empty nodes do not stack ）
            if (node->right) st.push(node->right); //  Empty nodes do not stack 
        }
        reverse(result.begin(), result.end()); //  After reversing the result, the order is left and right 
        return result;
    }
};

Sequence traversal

We need to borrow an auxiliary data structure called queue to realize , First in first out queue , According to the logic of traversal layer by layer , Instead, stack first out is suitable for simulating depth first traversal, that is, recursive logic

And this kind of sequence traversal is breadth first traversal in graph theory , It's just that we apply it to binary trees .

class Solution {
    
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
    
        queue<TreeNode*> que;
        if (root != NULL) que.push(root);
        vector<vector<int>> result;
        while (!que.empty()) {
    
            int size = que.size();
            vector<int> vec;
        //  Be sure to use a fixed size here size, Do not use que.size(), because que.size It's changing 
            for (int i = 0; i < size; i++) {
    
                TreeNode* node = que.front();
                que.pop();
                vec.push_back(node->val);
                if (node->left) que.push(node->left);
                if (node->right) que.push(node->right);
            }
            result.push_back(vec);
        }
        return result;
    }
};