关于二叉树中序遍历

今天日常刷Leetcode刷到了一个二叉树中序遍历的题。原题链接

通过示例可以很明显了解到何为中序遍历，同时打算用栈结构来实现。

中序遍历

可以看作将节点投影到一个水平坐标轴上，从原点开始向右遍历。

如图顺序为:H->D->I->B->E->J->A->F->K->C->G

栈

栈遵循先进后出的原则。

把栈想象成一个桶：a1先入栈，被压在最底下；然后a2再入栈，压在a1的上面……

如何取出里面的数据呢？拿走最上面的元素，也就是出栈。被压在最底下的元素最后才能被拿出来。

例如：入栈顺序 = 1, 2, 3, 4
出栈顺序 = 4, 3, 2, 1

明白概念之后就到了实现这个操作了。

思路

我使用了栈结构以及访问标记来实现。每个节点都附带一个名为visited的bool值（默认false)。

先让根节点入栈（栈里面没元素怎么出栈）

然后一直循环直到栈内元素全部出来。

中途如果发现是空节点就continue回到循环开始的地方。

如果这个节点没被访问过，那么就先标记一下已被访问visited=true。

然后分别按顺序让右节点->当前节点->左节点入栈。（因为要中序遍历，所以如此入栈后出栈的顺序就是左节点->当前节点->右节点）

如果当前节点已经访问过了，那么就直接返回当前节点的值。

代码 (C++)

#include <vector>
#include <iostream>
#include <stack>
#include <unordered_map>
using namespace std;

//二叉树定义
struct TreeNode
{
	int val;
	TreeNode* left;
	TreeNode* right;
	TreeNode() : val(0), left(nullptr), right(nullptr) {}
	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
	TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
};


class Solution
{
public:
	vector<int> inorderTraversal(TreeNode* root)
	{
		stack<TreeNode*> s;   //栈，存储每个节点的地址
		unordered_map<TreeNode*, bool> umap{{nullptr, false}};  //visited表，判断当前节点是否访问过，初始化全为false
		vector<int> res;   //答案结果
		s.push(root);   //根节点入栈
		TreeNode* temp;   //当前节点
		while (!s.empty())
		{
			temp = s.top();
			s.pop();            //取得栈顶的元素
			if (!temp) continue;  //节点为空就continue
			if (umap[temp]) res.push_back(temp->val);     //当前节点已被访问过，返回节点的值
			else
			{
				umap[temp] = true;      //标记已被访问
				s.push(temp->right);
				s.push(temp);
				s.push(temp->left);
			}
		}
		return res;
	}
};