樹的“最近公共祖先”問題，面試不再怕了！
本文所列題目來自 LeetCode 中國網(wǎng)站，屬于算法面試中關(guān)于二叉樹的經(jīng)典高頻考題（求二叉樹的最近公共祖先）。題解由 Doocs 開源社區(qū) leetcode 項目維護(hù)者提供。
目前已經(jīng)有超過 50 位開發(fā)者參與了此項目，期待你的加入！
項目地址：https://github.com/doocs/leetcode
題目 1
題目描述
二叉樹的最近公共祖先。
給定一個二叉樹, 找到該樹中兩個指定節(jié)點的最近公共祖先。
百度百科中最近公共祖先的定義為：“對于有根樹 T 的兩個結(jié)點 p、q，最近公共祖先表示為一個結(jié)點 x，滿足 x 是 p、q 的祖先且 x 的深度盡可能大（一個節(jié)點也可以是它自己的祖先）?！?/p>
例如，給定如下二叉樹:? root =?[3,5,1,6,2,0,8,null,null,7,4]
示例 1:
輸入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1輸出: 3解釋: 節(jié)點 5 和節(jié)點 1 的最近公共祖先是節(jié)點 3。
示例 ?2:
輸入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4輸出: 5解釋: 節(jié)點 5 和節(jié)點 4 的最近公共祖先是節(jié)點 5。因為根據(jù)定義最近公共祖先節(jié)點可以為節(jié)點本身。
說明:
?所有節(jié)點的值都是唯一的。?p、q 為不同節(jié)點且均存在于給定的二叉樹中。
解法
根據(jù)“最近公共祖先”的定義，若 root 是 p, q 的最近公共祖先 ，則只可能為以下情況之一：
?如果 p 和 q 分別是 root 的左右節(jié)點，那么 root 就是我們要找的最近公共祖先；?如果 p 和 q 都是 root 的左節(jié)點，那么返回?lowestCommonAncestor(root.left, p, q)；?如果 p 和 q 都是 root 的右節(jié)點，那么返回?lowestCommonAncestor(root.right, p, q)。
邊界條件討論：
?如果 root 為 null，則說明我們已經(jīng)找到最底了，返回 null 表示沒找到；?如果 root 與 p 相等或者與 q 相等，則返回 root；?如果左子樹沒找到，遞歸函數(shù)返回 null，證明 p 和 q 同在 root 的右側(cè)，那么最終的公共祖先就是右子樹找到的結(jié)點；?如果右子樹沒找到，遞歸函數(shù)返回 null，證明 p 和 q 同在 root 的左側(cè)，那么最終的公共祖先就是左子樹找到的結(jié)點。
Python3
# Definition for a binary tree node.# class TreeNode:# def __init__(self, x):# self.val = x# self.left = None# self.right = Noneclass Solution:def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:if root is None or root == p or root == q:return rootleft = self.lowestCommonAncestor(root.left, p, q)right = self.lowestCommonAncestor(root.right, p, q)return right if left is None else (left if right is None else root)
Java
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode(int x) { val = x; }* }*/class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if (root == null || root == p || root == q) {return root;}TreeNode left = lowestCommonAncestor(root.left, p, q);TreeNode right = lowestCommonAncestor(root.right, p, q);return left == null ? right : (right == null ? left : root);}}
題目 2
題目描述
二叉搜索樹的最近公共祖先。
給定一個二叉搜索樹, 找到該樹中兩個指定節(jié)點的最近公共祖先。
百度百科中最近公共祖先的定義為：“對于有根樹 T 的兩個結(jié)點 p、q，最近公共祖先表示為一個結(jié)點 x，滿足 x 是 p、q 的祖先且 x 的深度盡可能大（一個節(jié)點也可以是它自己的祖先）。”
例如，給定如下二叉搜索樹:? 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解釋: 節(jié)點 2 和節(jié)點 8 的最近公共祖先是 6。
示例 2:
輸入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4輸出: 2解釋: 節(jié)點 2 和節(jié)點 4 的最近公共祖先是 2, 因為根據(jù)定義最近公共祖先節(jié)點可以為節(jié)點本身。
說明:
?所有節(jié)點的值都是唯一的。?p、q 為不同節(jié)點且均存在于給定的二叉搜索樹中。
解法
從上到下搜索，找到第一個值位于?[p, q]?之間的結(jié)點即可。既可以用迭代實現(xiàn)，也可以用遞歸實現(xiàn)。
Python3
?迭代法
# Definition for a binary tree node.# class TreeNode:# def __init__(self, x):# self.val = x# self.left = None# self.right = Noneclass Solution:def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:if p == q:return pwhile root:if root.val < p.val and root.val < q.val:root = root.rightelif root.val > p.val and root.val > q.val:root = root.leftelse:return root
?遞歸法
# Definition for a binary tree node.# class TreeNode:# def __init__(self, x):# self.val = x# self.left = None# self.right = Noneclass Solution:def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':if root.val < p.val and root.val < q.val:return self.lowestCommonAncestor(root.right, p, q)if root.val > p.val and root.val > q.val:return self.lowestCommonAncestor(root.left, p, q)return root
Java
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode(int x) { val = x; }* }*/class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if (p == q) {return p;}while (root != null) {if (root.val < p.val && root.val < q.val) {root = root.right;} else if (root.val > p.val && root.val > q.val) {root = root.left;} else {return root;}}return null;}}
全文完！
希望本文對大家有所幫助。如果感覺本文有幫助，有勞轉(zhuǎn)發(fā)或點一下“在看”！讓更多人收獲知識！
長按識別下圖二維碼，關(guān)注公眾號「Doocs 開源社區(qū)」，第一時間跟你們分享好玩、實用的技術(shù)文章與業(yè)內(nèi)最新資訊。