用一个函数解决二叉树前中后序的非递归遍历问题

思路就是直接使用二叉树的经典二级结论, 第一次遍历到就输出即为前序, 第二次为中序, 第三次为后序.

#include <iostream>
#include <stack>

struct Node {
	Node *lchild, *rchild;
	int data;
	int times;
	Node(int d) : data(d), lchild(nullptr), rchild(nullptr), times(-1){}
};

void func(Node* root) {
	std::stack<Node*> s;
	s.push(root);

	Node* p = nullptr;
	while (!s.empty()) {
		p = s.top();
		++p->times;

		if (p->times == 2) {
			s.pop();		
		}
		else if (p->times == 1) {
			if (p->rchild) s.push(p->rchild);
		}
		else {
			if (p->lchild) s.push(p->lchild);
			std::cout << p->data << " ";
		}
		
	}
}

int main() {
	Node* root = new Node(0);
	Node* l = root->lchild = new Node(1);
	Node* r = root->rchild = new Node(2);
	l->lchild = new Node(3);
	l->rchild = new Node(4);
	r->lchild = new Node(5);
	r->rchild = new Node(6);

	func(root);
	return 0;
}

作为优化, 可以专门开一个mark数组来记录栈中元素被访问的次数, 而非在node节点添加一个新的数据成员.

‍之前一直纠结到底怎么方便地模拟递归. 递归相比正常地循环, 我看了其他人的代码, 区别就在于循环是一次性入栈左右节点, 而递归是左左左左左, 右右右右右, 中间, 这样的模式. 所以正解应该是: 用一个额外的存储空间来记录当前节点被访问的次数, 从而实现每次循环只入栈一个节点. 不过这种模式无法直接迁移到别的递归函数中. 在别的递归函数中会改变的地方是, 它们不一定是使用times来判断, 而是使用别的标准. 然而想出这种模式后, 我认为很多递归函数都可以以此为启发来实现非递归版本. 只要搞清楚判断即可.