1. 题目

给定一个二叉树，找到该树中两个指定节点的最近公共祖先

最近公共祖先的定义为：对于有根树T的两个节点p、q，最近公共祖先表示为一个节点x，满足x是p、q的祖先且x的深度尽可能大（一个节点也可以是它自己的祖先）

示例1：

  1. 输入：root = [3, 5, 1, 6, 2, 0, 8, nil, nil, 7, 4], p = 5, q = 1
  2. 输出：3

image.png
方法：

  1. //最近公共祖先
  2.     func nearestCommonAncestor(root : TreeNode?,p : Int,q : Int) -> TreeNode? {
  3.         if root == nil {
  4.             return nil
  5.         }
  7.         if root?.val == q || root?.val == p {
  8.             return root!
  9.         }
  11.         let left =  nearestCommonAncestor(root: root?.left, p: p, q: q)
  12.         let right = nearestCommonAncestor(root: root?.right, p: p, q: q)
  14.         if left == nil  {
  15.             return right
  16.         }
  18.         if right == nil {
  19.             return left
  20.         }
  21.         return root!
  22.     }