LeetCode 235： 二叉搜尋樹的最近公共祖先

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

題目描述：

給定一個二叉搜尋樹, 找到該樹中兩個指定節點的最近公共祖先。

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

例如，給定如下二叉搜尋樹:  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, 因為根據定義最近公共祖先節點可以為節點本身。
      

連結：

235. 二叉搜尋樹的最近公共祖先 - 力扣（LeetCode） (leetcode-cn.com)

解題思路 

二叉搜尋樹的特點就是 左子樹的所有節點都小于目前節點，右子樹的所有節點都大于目前節點，并且每棵子樹都具有上述特點

思路一：非遞歸解決

• 如果兩個節點值都小于根節點，說明他們都在根節點的左子樹上，我們往左子樹上找
• 如果兩個節點值都大于根節點，說明他們都在根節點的右子樹上，我們往右子樹上找
• 如果一個節點值大于根節點，一個節點值小于根節點，說明他們他們一個在根節點的左子樹上一個在根節點的右子樹上，那麼根節點就是他們的最近公共祖先節點

/**
 * @param {TreeNode} root
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {TreeNode}
 */
var lowestCommonAncestor = function(root, p, q) {
  // 如果根節點和p,q的差相乘是正數，說明這兩個內插補點要麼都是正數要麼都是負數，也就是說
  // 它們肯定都位于根節點的同一側，就繼續往下找
  while ((root.val - p.val) * (root.val - q.val) > 0)
      root = p.val < root.val ? root.left : root.right;
  // 如果相乘的結果是負數，說明p和q位于根節點的兩側，如果等于0，說明至少有一個就是根節點
  return root;
};
           

時間複雜度： O(n)

空間複雜度： O(1)

思路二：遞歸解決

/**
 * @param {TreeNode} root
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {TreeNode}
 */
var lowestCommonAncestor = function(root, p, q) {
  // 如果小于等于0，說明p和q位于root的兩側，直接傳回即可
  if ((root.val - p.val) * (root.val - q.val) <= 0) return root;
  // 否則，p和q位于root的同一側，就繼續往下找
  return lowestCommonAncestor(p.val < root.val ? root.left : root.right, p, q);
}; 
           

時間複雜度：O(n)

空間複雜度：O(1)

參考資料：

力扣