二叉树dfs遍历 & 给定中/后序，生成前序

树上 DFS

在树上 [[DFS]] 是这样的一个过程：先访问根节点，然后分别访问根节点每个儿子的子树。
可以用来求出每个节点的深度、父亲等信息。

先序遍历

按照 根，左，右 的顺序遍历二叉树

void preorder(BiTree* root) { 
	if (root) { 
		cout << root->key << " "; 
		preorder(root->left); 
		preorder(root->right); 
	}
}

中序遍历

按照 左，根，右 的顺序遍历二叉树。

后序遍历

按照 左，右，根 的顺序遍历二叉树。

已知后序和中序，重构二叉树：build_tree(0, n, 0, n)

int border[SZ], morder[SZ];
int build_tree(int s1, int e1, int s2, int e2) {
	if (s1 >= e1 || s2 >= e2) return -1; // 空树情况

	int root = border[e1 - 1]; // 后序遍历的最后一个元素是根
	int mid = -1;
	for (int i = s2; i < e2; i++) {
		if (morder[i] == root) {
			mid = i;
			break;
		}
	}

	// 左子树的后序遍历起止位置和中序遍历起止位置
	lch[root] = build_tree(s1, s1 + mid - s2, s2, mid);
	// 右子树的后序遍历起止位置和中序遍历起止位置
	rch[root] = build_tree(s1 + mid - s2, e1 - 1, mid + 1, e2);
	return root;
}

update 2024/3/13
其实递归函数的参数用一个区间就可以了，然后加一个t表示当前在前序/后序的节点

int in[SZ], pre[SZ];
int n, cnt;

struct node {
	int v;
	node *lch, *rch;
	node(int i): v(i), lch(nullptr), rch(nullptr) {}
};

//t表示当前在前序的第t个node
void buildTree(int l, int r, int &t, node* &root) {
	int id = -1;

	//在中序中找到根节点
	for(unsigned i = l; i < r; ++i) {
		if (in[i] == pre[t]) {
			id = i;
			break;
		}
	}

	if (id == -1)
		return;

	root = new node(in[id]);
	t++; //前序往后一个

	if (id > l)
		buildTree(l, id, t, root->lch); //取到id-1个，id是从0开始数的
	if (id < r)
		buildTree(id, r, t, root->rch);
}