图解LeetCode——剑指 Offer 68 - I. 二叉搜索树的迩来公共先人

对于有根树 T 的两个结点 p、q，迩来公共先人体现为一个结点 x，满意 x 是 p、q 的先人且 x 的深度尽大概大（一个节点也可以是它自己的先人）。

【输入】 root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
【输出】 6
【解释】 节点 2 和节点 8 的迩来公共先人是 6。

【输入】 root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
【输出】 2
【解释】 节点 2 和节点 4 的迩来公共先人是 2, 因为根据界说迩来公共先人节点可以为节点自己。

• 全部节点的值都是唯一的。
  
• p、q 为差异节点且均存在于给定的二叉搜索树中。
  

【若它的左子树不空】则左子树上全部结点的值均小于它的根结点的值；
【若它的右子树不空】则右子树上全部结点的值均大于它的根结点的值；

【情况1】当根节点的值处于p节点的值和q节点的值之间时，那么根节点就是迩来公共先人节点。
【情况2】当根节点的值大于p节点的值和q节点的值时，那么我们只必要遍历根节点的左子树，然后第一个遍历到的节点就是迩来公共先人节点。
【情况3】当根节点的值小于p节点的值和q节点的值时，那么我们只必要遍历根节点的右子树，然后第一个遍历到的节点就是迩来公共先人节点。
【留意】每当遍历到一个子树的根节点时，都必要对比上面的3种情况，来决定实行那块逻辑。