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

題目描述：給定一個二叉搜索樹, 找到該樹中兩個指定節(jié)點的最近公共祖先。

百度百科中最近公共祖先的定義為：“對于有根樹 T 的兩個結(jié)點 p、q，最近公共祖先表示為一個結(jié)點 x，滿足 x 是 p、q 的祖先且 x 的深度盡可能大（一個節(jié)點也可以是它自己的祖先）。”

示例說明請見LeetCode官網(wǎng)。

來源：力扣（LeetCode） ??

鏈接：https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-search-tree/ ??

著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

解法一：遞歸法

• 首先，如果p或q是根節(jié)點，直接返回根節(jié)點。

• 如果p和q都不是根節(jié)點，則分以下幾種情況處理：

• 如果p和q的值都小于root的值，則遞歸調(diào)用該方法lowestCommonAncestor，入?yún)?root.left。

• 如果p和q的值都小于root的值，則遞歸調(diào)用該方法lowestCommonAncestor，入?yún)?root.right。

• 如果p和q一個大于root的值，另一個小于root的值，則p和q的最近公共祖先只可能是root，所以直接返回root。

【每日寄語】 不是境況造就人，而是人造就境況。