---

前言

本次数据结构课也是不出我所料留的题有点难度。这两道题都可以加深对树的理解和操作。

---

一、根据后序中序确定前序

首先我们要明白，二叉树中根据前序和中序 或者 中序和后序也就是说-----中序和另外一个序列就可以确定树的结构-----为什么？？？？无论是前序还是后序都能确定根的位置，中序通过确定根分为左右子树，递归下去即可得到树的结构。

1.根据两种遍历顺序确定一棵树的结构。给出一棵二叉树的中序与后序排列。求出它的先序排列。(约定树结点用不同的大写字母表示，长度≤8)。

输入格式：第一行为二叉树的中序序列，第二行为二叉树的后序序列
输出格式：一行，为二叉树的先序序列

样例输入：
BADC
BDCA
样例输出：
ABCD
思路：递归 后序是左右根,因此后序的最后一个元素一定是根节点
而中序是左根右，找到了根的位置就可以递归去连接左子树和右子树
比如：中序：BADC 后序：BDCA
找到这个A说明为根节点,找到A在中序的位置,B就是A的左子树,DC就属于A的右子树，递归下去,后序的倒数第二个下标是C,找到C在中序的位置,递归下去…
由于需要快速获取某个字符在中序中的位置,需要我们维护一个哈希表,即元素和下标的位置即可。

#include<bits/stdc++.h>
#include<unordered_map>
using namespace std;
struct Node{
    char val;
    Node* left,*right;

    Node(int v)
        :val(v),left(nullptr),right(nullptr)
    {}
};
string str1,str2;
unordered_map<char,int> mp;
int pos; //维护下标,初始化是str2.size() - 1,也就是维护根节点下标
Node* CreateTree(int left,int right)
{
    if(left > right) return nullptr;
    
    char rootval = str2[pos];
    Node* newnode = new Node(rootval);

    int idx = mp[rootval]; //找寻根节点在中序中的位置
    pos--;

    newnode->right = CreateTree(idx + 1,right);

    newnode->left = CreateTree(left,idx - 1);

    return newnode;
}

void PrevOrder(Node* node)
{
    if(node == nullptr) return;
    cout << node->val;
    PrevOrder(node->left);
    PrevOrder(node->right);
}
int main()
{
    getline(cin,str1);
    getline(cin,str2);
    //输入中序和后序序列

    int idx = 0;
    for(char e:str1)  mp[e] = idx++;
    pos = str2.size() - 1;
    Node* root = CreateTree(0,str2.size() - 1);

    PrevOrder(root);
    return 0;
}

二、lca问题(公共祖先问题)

给定一棵树，同时给出树中的两个结点(n1和n2)，求它们的最近公共祖先。
这里给出三种思路

1.找路径

思路：
（1）找到从根到n1的路径，并存储在栈中
（2）找到从根到n2的路径，并存储在另一个栈中
（3）这两个栈存着他们倒着的路径，先让size大的pop到和另一个size一样，同时pop，相等就是lca
这个过程很好想比如一个是9 4 5 1，另一个是9 4，出掉5 1，4就是lca
问题是怎么找到路径，这里用栈比较合适，发现这个节点不符合要求就pop掉，进来的节点先push

    bool Find(TreeNode*node,TreeNode* find,stack<TreeNode*>& st)
    {
        if(node == nullptr) return false;
        st.push(node);
        if(find == node) return true;
        if(Find(node->left,find,st)) return true;
        if(Find(node->right,find,st)) return true;
        st.pop();
        return false;
    }
    TreeNode* GetLca(TreeNode* root, TreeNode* p, TreeNode* q)  {
      stack<TreeNode*> stp,stq;
      Find(root,p,stp);
      Find(root,q,stq);
      if(stp.size() < stq.size()) stp.swap(stq);
      //3 5   3 1 
      while(stp.size() != stq.size()) stp.pop();
      while(stp.top() != stq.top())
      {
        stp.pop(),stq.pop();
      }

      return stp.top();
    }

时间复杂度:O(N)

2.递归

可能不太好想，结合注释来看还是可以理解的。

TreeNode *GetLca(TreeNode *root, TreeNode *p, TreeNode *q)
{

    if (!root || root == p || root == q) return root;
    //左子树找p或者q
    TreeNode *left = GetLca(root->left, p, q);
    //右子树找p或者q
    TreeNode *right = GetLca(root->right, p, q);

    //如果都找到了，说明根就是lca
    if (left && right) return root;
    //没找到,返回上一层
    return left ? left : right;
}

时间复杂度:O(N)

---

3.倍增求LCA

这个做法是比较多的做法，因为构建完成之后每次查询的时间复杂度都是logN
板子：

//第二种思路：倍增求lca,构建完是nlogN,之后每次查询都是logN
const int mod = 1e9 + 7;
const int N = 1e5 + 1;
vector<int> g[N];
int fa[N][24],dep[N];
int lca(int x,int y)
{
  if(dep[x] < dep[y]) swap(x,y);
  for(int i = 20;i >= 0;i --)
  {
    if(dep[fa[x][i]] >= dep[y]) x = fa[x][i];
  }
  if(x == y) return x;

  for(int i = 20;i >= 0;--i) if(fa[x][i] != fa[y][i]) x = fa[x][i],y = fa[y][i];
  return fa[x][0];
}
void dfs(int x,int f)
{
  dep[x] = dep[f] + 1;
  fa[x][0] = f;
  for(int i = 1;i <= 20;i++) fa[x][i] = fa[fa[x][i - 1]][i - 1];

  for(const auto& y:g[x])
  {
    if(y == f)continue;
    dfs(y,x);
  }
}

void solve()
{
  int n;cin >> n;
  while(--n)
  {
    int x,y;cin >> x >> y;
    g[x].push_back(y),g[y].push_back(x);
  }
  int m;cin >> m;
  dfs(1,1);
  while(m--)
  {
    int x,y;
    cin >> x >> y;
    cout << lca(x,y) << endl;
  }
}

OiWiki
OiWiki里面给的比较详细，也有思路，想看可以看一看。
时间复杂度:O(NlogN + MlogN) M代表查询的次数,N是节点个数。