1. 在线算法：指这个算法可以实时根据输入计算出输出，可以一个个的进行输入输出，并不需要所有的输入数据，
  2. 离线算法：在算法开始前，需要获得所有的输入数据

问题描述：给定一个二叉树，找到该书中两个指定节点的最近公共祖先

  1. 最近公共祖先：对于树T的两个节点p、q，最近公共祖先表示为一个节点x，满足x时p、q的祖先且x的深度尽可能大

朴素算法

  • 因为两个点都在树上，这两个点最后一定会相遇，首先找深度较大的那个点，然后让他往上跳，直到两个点的深度相同，然后再让这两个点同时向上跳，直到相遇，相遇点就是要求的LCA点
  • 可以通过回溯遍历实现,最坏的时间复杂度是O(n)

Tarjan算法

算法流程

Procedure dfs（u）；
begin
设置u号节点的祖先为u
若u的左子树不为空，dfs（u - 左子树）；
若u的右子树不为空，dfs（u - 右子树）；
访问每一条与u相关的询问u、v
-若v已经被访问过，则输出v当前的祖先t（t即u,v的LCA）
标记u为已经访问，将所有u的孩子包括u本身的祖先改为u的父亲
end