#include<bits/stdc++.h> using namespace std; int temp[100001]; struct Tree { int data; struct Tree* lchild; struct Tree* rchild; }; //二叉搜索树插入 void _insert(struct Tree* &root, int t) { if(root == NULL) { root = new Tree; root->data = t; ...

这个题目做法是o(n)的，但是网上流传了大量o(nlogn)甚至o(n^2)的伪算法 首先，二叉搜索树的所有节点是从左到右的，按顺序插入的节点一定不可能排在父节点前面。 于是我们将节点放在二维平面内，a[i]坐标为(a[i],i)，i越小，高度越高 可以证明两个结论： 1.二叉查找树两个节点i,j若互相不为对方的祖先，则有最近公共祖先x，a[i]与a[j]一个比a[x]大，一个比a[x]小。 反证：如果两个都比a[x]大或者比a[x]小，则两个节点在x的同一个子树中，x不是最近公共祖先。 2.数值上处于任何一个节点的父节点及其本身之间的所有节点都是其子...