[middle order traversal of binary tree based on stack] middle order traversal of binary tree + stack, spatial complexity of O (H)

【 Stack based traversal in binary tree 】 Middle order traversal of binary trees + Stack ,O(h) Time complexity of

In general, we usually use the recursive algorithm to traverse the binary tree , The template is as follows ：

void dfs(TreeNode *root){
    
	if(!root)return;
	dfs(root->left);
	cout<<root->val<<endl;
	dfs(root->right);
}

The time complexity of the algorithm is O（n）, If random access to binary tree is required , You need to use an array to flatten the binary tree , The space complexity is O（n）

stay Leetcode The finger of the sword offer in , Learned a binary tree in order to traverse the algorithm , The algorithm combines the data structure of stack , Reduce space complexity to O(h),h Is the height of the binary tree .

The specific algorithm is as follows ：

int dfs(){
    
	while(!cur){
    
		sta.push(root);
		root = root->left;
	}
	cur = sta.top();
	int res = cur->val;
	cur = cur->right;
	return res;
}

Then the algorithm can realize that for a given binary tree, the algorithm can return a middle order traversal value every time it is called .