摘要
Title: 1631. 后序遍历
Tag: 二叉树、后序遍历
Memory Limit: 64 MB
Time Limit: 1000 ms

Powered by:NEFU AB-IN

Link

• 题意
• 思路
• 代码

1631. 后序遍历

• 题意

  假设二叉树上各结点的权值互不相同且都为正整数。
  给定二叉树的前序遍历和中序遍历，请你输出二叉树的后序遍历的第一个数字。

• 思路

  已知前序和中序，求后序
  各节点的值不同，故可用哈希表优化

• 代码

  /*
  * @Author: NEFU AB-IN
  * @Date: 2022-04-19 22:39:04
  * @FilePath: \ACM\Acwing\1631.cpp
  * @LastEditTime: 2022-04-19 22:50:00
  */
  #include <algorithm>
  #include <cstring>
  #include <iostream>
  #include <unordered_map>
  
  using namespace std;
  
  const int N = 1e5 + 10;
  int preorder[N], inorder[N];
  int n, post;
  
  unordered_map<int, int> pos;
  
  void build(int il, int ir, int pl, int pr)
  {
      int root = preorder[pl];
      int k = pos[root];
      if (il < k)
          build(il, k - 1, pl + 1, pl + 1 + k - 1 - il);
      if (ir > k)
          build(k + 1, ir, pl + 1 + k - 1 - il + 1, pr);
      if (!post)
          post = root;
  }
  
  int main()
  {
      cin >> n;
      for (int i = 0; i < n; ++i)
      {
          cin >> preorder[i];
      }
      for (int i = 0; i < n; ++i)
      {
          cin >> inorder[i];
          pos[inorder[i]] = i;
      }
      build(0, n - 1, 0, n - 1);
      cout << post;
  }