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

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

朴素算法

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