PAT (Advanced Level)1020. Tree Traversals (25) 队列 二叉树的遍历

题目链接

//1020. Tree Traversals(25)#include  
#include  
#include  
using namespace std;const int maxn = 1e3 + 10;
int n, a[maxn], b[maxn], ch[maxn][2], root;void dfs(int&x, int l, int r, int ll, int rr)//关键在用ch二维数组记录根节点
{if (l > r) x = 0;//递归结束时，返回整棵树的树根for (int i = l; i <= r; i++){if (a[i] == b[rr]){x = i;dfs(ch[x][0], l, i - 1, ll, ll + i - l - 1);//以x为根的左子树递归遍历。两边长度相等，左边（i-1-l+1）,右边定下ll后，即可定。下同。dfs(ch[x][1], i + 1, r, ll + i - l, rr - 1);//以x为根的右子树递归遍历}}
}int main()
{cin >> n;;for (int i = 1; i <= n; i++) cin >> b[i];//后序遍历for (int i = 1; i <= n; i++) cin >> a[i];//中序遍历dfs(root, 1, n, 1, n);queue p; p.push(root);//cout << root<

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！