二叉搜索树的最近公共祖先

1. 题目描述

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

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

2. 示例

例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]

示例1

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
输出: 6 
解释: 节点 2 和节点 8 的最近公共祖先是 6。

示例2

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
输出: 2
解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。

说明

所有节点的值都是唯一的。
p、q 为不同节点且均存在于给定的二叉搜索树中。

3. 解题

递归分析其遍历序列
对于上述例子中的树，其先序，中序遍历序列分别为：

pre: 6, 2, 0, 4, 3, 5, 8, 7, 9
 in: 0, 2, 3, 4, 5, 6, 7, 8, 9

构造如下函数：
首先求rootIndex：root节点在中序序列中的位置。

若要求的两个节点在root节点两侧，或是其中一个节点等于root，则说明这两个节点的公共祖先即为rootIndex
若两个节点在同一侧
- 在左侧，则进行递归，此时pre = pre[1 : rootIndex+1], in = in[0 : rootIndex]
- 在右侧，进行递归，此时pre = pre[rootIndex+1 : ], in = in[rootIndex : ]

则对上述例子中的树的求解过程如下：

example1:
目标节点: 2, 4
第一次递归：
   pre: 6, 2, 0, 4, 3, 5, 8, 7, 9
    in: 0, 2, 3, 4, 5, 6, 7, 8, 9
   rootIndex = 5, rootVal = 6
   2和4均小于6，也即在rootIndex左边，进行递归

第二次递归
   pre: 2, 0, 4, 3, 5
    in: 0, 2, 3, 4, 5
   rootIndex = 1, rootVal = 2
   目标节点2与rootIndex表示节点想等，则当前节点即为其公共祖先

-------------------------------------------------------

example1:
目标节点: 3, 5
第一次递归：
   pre: 6, 2, 0, 4, 3, 5, 8, 7, 9
    in: 0, 2, 3, 4, 5, 6, 7, 8, 9
   rootIndex = 5, rootVal = 6
   3和5均小于6，也即在rootIndex左边，进行递归

第二次递归
   pre: 2, 0, 4, 3, 5
    in: 0, 2, 3, 4, 5
   rootIndex = 1, rootVal = 2
   3和5均大于2，也即在rootIndex右边，进行递归

第三次递归
pre: 4, 3, 5
 in: 3, 4, 5
rootIndex = 1, rootVal = 4
3和5分别在4的两边，因此4为他们的公共祖先。

递归对比直接对比root.Val 和 p.Val, q.Val

若一个大于root.Val一个小于root.Val，则root即为其公共祖先
若其中一个等于root.Val, 则root即为其公共祖先
若在左侧或右侧，递归分析

# README

二叉搜索树的最近公共祖先

1. 题目描述

2. 示例

3. 解题