二叉树相关问题：二叉树的深度，通过前序遍历和中序遍历求出后序遍历

一、二叉树的深度

我们通过递归求出树中以每个结点为根节点的左子树和右子树的最大深度。以下图为例从C结点开始，首先求C结点的左子树的深度，C结点的左子树的深度等于B结点的左子树的深度+1，这样层层递归，当递归到A结点时返回深度为1。右子树深度同理

代码如下：

#include<iostream>
using namespace std;

#define MAX 1000010

struct Node{
	int left;
	int right; 
};
Node tree[MAX];

int treeDepth(Node root){
    if(root.left==0&&root.right==0){ //为叶子结点 
        return 1;
    }
    int nLeft=treeDepth(tree[root.left]); //左子树深度
    int nRight=treeDepth(tree[root.right]); //右子树深度
    return nLeft>nRight?nLeft+1:nRight+1;
}

int main(){
	int n;
	cin>>n;
	int left,right;
	for(int i=1;i<=n;i++){
		cin>>tree[i].left>>tree[i].right;
	}
	
	int res=treeDepth(tree[1]);
	cout<<res<<endl;
}

二、前序遍历&后续遍历=>后续遍历

中序遍历：ABEDFCHG
前序遍历：CBADEFGH
前序遍历的第一个结点一定为根节点，我们找到该结点在中序遍历中的位置。那么该结点所在位置的左侧ABEDF就是根节点的左子树，右侧HG就是根节点的右子树。后序遍历先访问左子树，因此接着访问ABEDF，从前序遍历BADEF中可以看出B为根节点，因此左侧A就是A的左子树，右侧EDF就是B的右子树。接着访问A，它的长度为1，直接输出。
代码如下：

#include<iostream>
#include<string> 
using namespace std;

void run(string A, string B);

int main() {
	string a;  //中序遍历
	cin >> a;
	string b;  //谦虚遍历
	cin >> b;
	run(a, b);
}

void run(string A, string B) {
	if (A.length() == 0) {
		return;
	}
	if (A.length() == 1) {
		cout << A[0];
		return;
	}
	run(A.substr(0, A.find(B[0])), B.substr(1, A.find(B[0])));
	run(A.substr(A.find(B[0]) + 1), B.substr(A.find(B[0]) + 1));
	//根据后序遍历的顺序，最后再输出根节点的元素值
	cout << B[0];
}