C++&&数据结构——二叉树的非递归遍历

前序非递归遍历

题目出处：144. 二叉树的前序遍历 - 力扣（LeetCode）

有了C++的STL和前面大量学习的支持，我们可以来实现二叉树的非递归遍历了！

二叉树的非递归遍历思路大体如下：

①将一棵树分成左路节点和左路节点的右子树两部分

②用一个栈存储左路节点，目的是访问每个节点的右子树

③然后以子问题访问右子树，将访问的右子树转化为一个个小的左路节点和左路节点的右子树两部分，然后循环

具体实现结合下面代码和注释：

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
    stack<TreeNode*> st; //创建一个栈来存左路节点，目的是访问栈中每个节点的右子树
	TreeNode* cur = root;
	vector<int> v;
	while (cur || !st.empty())
	{
		//每次循环访问一棵树
		//1，左路节点
		//2，左路节点的右子树
		while (cur)
		{
			v.push_back(cur->val); //前序遍历先访问最左路基节点
			st.push(cur);          //将左路节点入栈
			cur = cur->left;
		}
		//开始访问右子树
		TreeNode* top = st.top();
		st.pop();

		//子问题访问右子树 -- 将访问右子树转化为一个个小的左路节点入栈，同时完成访问
		cur = top->right;
	}
	return v;
    }
};

中序非递归遍历

题目出处：94. 二叉树的中序遍历 - 力扣（LeetCode）

中序遍历的思路和前序大体类似，如下代码：

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
    stack<TreeNode*> st;
	TreeNode* cur = root;
	vector<int> v;
	while (cur || !st.empty())
	{
		while (cur)
		{
			st.push(cur);          //将左路节点入栈
			cur = cur->left;
		}
		//栈里面取左路节点，表示该节点左子树访问完了
        v.push_back(st.top()->val);
        cur = st.top()->right;
		st.pop();
	}
	return v;
    }
};

后续非递归遍历

题目出处：145. 二叉树的后序遍历 - 力扣（LeetCode）

改造前序非递归遍历

我们可以直接改造前序非递归遍历的代码，前序遍历是根左右，我们直接改成根右左访问，然后逆置以下即可，这属于一种取巧的思路，如下代码：

class Solution
{
	vector<int> postorderTraversal(TreeNode* root)
	{
		stack<TreeNode*> st; //创建一个栈来存左路节点，目的是访问栈中每个节点的右子树
		TreeNode* cur = root;
		vector<int> v;
		while (cur || !st.empty())
		{
			while (cur)
			{
				v.push_back(cur->val);
				st.push(cur);
				cur = cur->right;
			}
			//开始访问左子树
			TreeNode* top = st.top();
			st.pop();
			cur = top->left;
		}
		reverse(v.begin(), v.end());
		return v;
	}
};

用原来的思路实现

class Solution {
public:
	vector<int> postorderTraversal(TreeNode* root) {
		stack<TreeNode*> st;
		vector<int> v;
		TreeNode* prev = nullptr; //
		TreeNode* cur = root;
		while (cur || !st.empty())
		{
			while (cur) //不管三七二十一直接把左路入栈
			{
				st.push(cur);
				cur = cur->left;
			}
			TreeNode* top = st.top();
			//1，右为空，或者右子树已经访问过了（上一个+访问的是右子树的根），就可以访问根节点
			if (top->right == nullptr || top->right == prev)
			{
				v.push_back(top->val);
				prev = top;
				st.pop();
			}
			//
			else
			{
				cur = top->right;//子问题，访问右子树
			}
		}
		return v;
	}
};