题目

来源

23. 二叉树的高度

思路

其实跟09那篇很像，反正核心就是要通过前序和中序来建树，只不过现在多了一个返回值；因为建树的时候，其实左子树和右子树的深度就可以知道。其余详见代码。

代码

/*
前序遍历根左右,中序：左根右,后序：左右根
*/
#include<bits/stdc++.h>
using namespace std;
int dfs(string pre,string in){if(pre.empty())return 0;char root=pre[0];int k=in.find(root);int left=dfs(pre.substr(1,k),in.substr(0,k)); //遍历左子树int right=dfs(pre.substr(k+1),in.substr(k+1)); //遍历右子树return max(left,right)+1;
}int main(){string pre,in;int n;while(cin>>n){cin>>pre>>in;int height=dfs(pre,in);cout<<height<<endl;}return 0;
}