非递归实现二叉树的前、中、后序遍历

二叉树的前序遍历

题目链表：二叉树的前序遍历

题目描述

给你二叉树的根节点 root ，返回它节点值的 前序 遍历。

题目分析

非递归实现二叉树的前序遍历，这里可以先定义一个栈来存放给个节点。前序遍历的顺序是根左右，因此根据栈的后进先出原则，可以先将各个节点入栈，然后依次取出栈顶元素，将其再依次出栈，并遍历右子树中的节点。具体代码实现如下：

代码实现

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

二叉树的中序遍历

题目链接：二叉树的中序遍历

题目描述

给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。

题目分析

正常递归实现二叉树的中序遍历只需要按照左根右的顺序来实现即可，这里尝试非递归来实现二叉树的中序遍历。二叉树的中序遍历和前序类似，区别在于一个先入根节点一个先入左节点，注意入vector的时间即可，代码实现如下：

代码实现

vector<int> inorderTraversal(TreeNode* root) 
{
    
	vector<int> ret;
	stack<TreeNode*> st;
	TreeNode* cur = root;
	while (cur || !st.empty())
	{
    
		while (cur)
		{
    
			st.push(cur);
			cur = cur->left;
		}
		TreeNode* tmp = st.top();
		ret.push_back(tmp->val);
		st.pop();
		cur = tmp->right;

	}
	return ret;
}

二叉树的后序遍历

题目链接：二叉树的后序遍历

题目描述

给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历 。

题目分析

正常来说实现二叉树的后序遍历使用递归的方式很简单，按照左右根的顺序即可，但是如果这棵树的递归深度太深可能会导致栈溢出，使用非递归的方式便可以解决这个问题。如何非递归实现二叉树的后序遍历呢？和前序和中序遍历有一些区别，他需要先访问左节点和右节点再去访问根，于是这里需要做一个标记，是否已经访问过该节点的右子树节点，如果是则可以将根遍历，如果还没有访问，则需要先去访问右子树节点，代码实现如下：

代码实现

    vector<int> postorderTraversal(TreeNode* root) 
    {
    
	vector<int> ret;
	stack<TreeNode*> st;
	TreeNode* cur = root;
	TreeNode* prev = nullptr;
	while (cur || !st.empty())//两者都不为空时进入循环
	{
    
		while (cur)//节点不为空时，左子树节点入栈
		{
    
			st.push(cur);
			cur = cur->left;
		}
		TreeNode* tmp = st.top();
		if (tmp->right == nullptr || tmp->right == prev)
		{
    
			ret.push_back(tmp->val);
			prev = tmp;
			st.pop();
		}
		else
		{
    
			cur = tmp->right;
		}
	}
	return ret;
    }