1. 分治法

树是无环图。

将大规模问题拆分为若干个小规模的同类型问题去处理的算法思想。 把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即 子问题的解的合

• 什么样的结构合适用分治法？

二叉树：整棵树的左子树和右子树都是二叉树。二叉树的大部分题都可以使用分治法解决。
数组：一个大数组可以拆分为若干个不相交的子数组 归并排序，快速排序，都是基于数组的分治法 遇到二叉树的问题，就想想整棵树在该问题上的结果和左右孩子在该问题上的结果之间有什么联系。

• 二叉树考点。

考察形态：二叉树上求值，求路径
代表例题：http://www.lintcode.com/problem/subtree-with-maximum-average/
考点本质：深度优先搜索（Depth First Search）

考察形态：二叉树结构变化
代表例题：http://www.lintcode.com/problem/invert-binary-tree/
考点本质：深度优先搜索（Depth First Search）

考察形态：二叉查找树（Binary Search Tree）
代表例题：http://www.lintcode.com/problem/validate-binary-search-tree/
考点本质：深度优先搜索（Depth First Search）

不管二叉树的题型如何变化，很多考点都是基于树的深度优先搜索 前中后代表：根被遍历的位置

1.1 二叉树上求值(Maximum / Minimum / Average / Sum)，求路径(Paths)

1. 最小子树：给一棵二叉树, 找到和为最小的子树, 返回其根节点（不是根节点的和）。 输入输出数据范围都在int内。 保证只有一棵和最小的子树 并且给出的二叉树不是一棵空树

   遇到二叉树的问题，就想想整棵树在该问题上 的结果和左右孩子在该问题上的结果之间有什 么联系 树的和 = 根节点值 + 左子树和 + 右子树和
   
   
   

• 最近公共祖先

  给一棵二叉树和二叉树中的两个节点，找到这两个节点的最近公共祖先LCA。 两个节点的最近公共祖先，是指两个节点的所有父亲节点中（包括这两个节点），离这两个节点最近的公共的节点。 每个节点除了左右儿子指针以外，还包含一个父亲指针parent，指向自己的父亲。 指向父亲的指针很方便，我们不需要搜索，只需要反向顺藤摸 瓜，就可以找到从根节点到某子节点的路径 注意： • 这里输入的两个点是node objects，不是数字 • 自己可以是自己的祖先 。

  指向父亲的指针很方便，我们不需要搜索，只需要反向顺藤摸 瓜，就可以找到从根节点到某子节点的路径
  
  
  
  实在不会做，dfs找根节点到目标节点的路径。