Leetcode94. Middle order traversal of binary trees

LeetCode94. Middle order traversal of binary trees

1. problem

2. Ideas

（1） What is middle root traversal

（2） recursive

The same idea as before and after ！

（3） iteration

It takes a stack ！

a section ADL Pseudo code ！

Process simulation

3. Code implementation

（1） recursive

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

    vector<int> inorderTraversal(TreeNode* root) {
    
        vector<int> result;
        inOrder(root, result);
        return result;
    }
};

（2） iteration

class Solution{
    
	public:
		vector<int> inorderTraversal(TreeNode* root){
    
			vector<int> result;
			stack<TreeNode*> st;// Create a stack 
			TreeNode* cur = root;
			while(1)
			{
    
				while(cur != NULL){
    // Every time you join one , First judge whether it can go down left , If there is one, put 
				st.push(cur);// Down the left branch , The visited node is put on the stack 
				cur = cur->left;  
			}
			if(st.empty()) return result;// When the stack is empty, it returns ！
			cur = st.top();// If the last step cur->right Empty finger , Then here will continue to stack 
			st.pop();
			result.push_back(cur->val);
			cur = cur->right;
	}
}
};