---

树专题2(PAT)：

1.后序遍历

后序遍历

 

2.AVL树的根

AVl树的根

 

3.判断完全 AVL 树

判断完全 AVL 树

 

4.判断红黑树

判断红黑树

 

5.等重路径

等重路径

 

6.最大的一代

最大的一代

 

7.供应链总销售额

供应链总销售额

 

8.供应链最高价格

供应链最高价格

 

9.供应链最低价格

供应链最低价格

 

10.堆路径

堆路径

 

11.中缀表达式

中缀表达式

 

12.最低公共祖先

最低公共祖先

 

13.二叉树中的最低公共祖先

二叉树中的最低公共祖先

 

AC代码:

1.后序遍历

# include <bits/stdc++.h>
using namespace std;
const int N = 5e4 + 10;

int pre[N],mid[N],n;
unordered_map<int,int> M; // 记录某个点在中序序列的位置
vector<int> back;

void build(int ml,int mr,int pl,int pr){ // 建立对应区间的子树并记录该子树的后序序列
  if (mr < ml) return;
  
  int root = pre[pl];
  int k = M[root];
  
  // 建立左右子树并记录后序序列
  build(ml,k - 1,pl + 1,pl - ml + k);
  build(k + 1,mr,pr - mr + k + 1,pr);
  
  back.push_back(root);
}

int main (void){
  scanf("%d",&n);
  for (int i = 1; i <= n; ++i) scanf(...