在計(jì)算機(jī)科學(xué)中，特別是在數(shù)據(jù)結(jié)構(gòu)和算法領(lǐng)域，“最近公共祖先”（Lowest Common Ancestor，LCA）是一個(gè)在有根樹或有向無環(huán)圖中的概念。對于有根樹 ( T ) 的兩個(gè)結(jié)點(diǎn) ( p ) 和 ( q )，最近公共祖先指的是樹中的一個(gè)結(jié)點(diǎn) ( x )，滿足 ( x ) 是 ( p ) 和 ( q ) 的共同祖先，并且 ( x ) 的深度盡可能大。

在二叉樹中尋找最近公共祖先的算法可以分為兩種情況：

1. 二叉搜索樹（Binary Search Tree, BST）

在二叉搜索樹中，可以利用其特性簡化查找過程：

• 如果 ( p ) 和 ( q ) 分別位于當(dāng)前節(jié)點(diǎn)的左右兩側(cè)，則當(dāng)前節(jié)點(diǎn)即為 LCA。
• 如果 ( p ) 和 ( q ) 都在當(dāng)前節(jié)點(diǎn)的左側(cè)，則在其左子樹中繼續(xù)查找。
• 如果 ( p ) 和 ( q ) 都在當(dāng)前節(jié)點(diǎn)的右側(cè)，則在其右子樹中繼續(xù)查找。

2. 一般二叉樹

在一般的二叉樹中，沒有像 BST 那樣的順序關(guān)系，因此需要使用遞歸或者迭代的方法來遍歷樹并查找 LCA。

遞歸方法:

• 從根節(jié)點(diǎn)開始遞歸地搜索 ( p ) 和 ( q )。
• 如果當(dāng)前節(jié)點(diǎn)等于 ( p ) 或 ( q )，則返回當(dāng)前節(jié)點(diǎn)。
• 如果在左子樹中找到了 ( p ) 或 ( q )，則返回左子樹的結(jié)果。
• 如果在右子樹中找到了 ( p ) 或 ( q )，則返回右子樹的結(jié)果。
• 如果左子樹和右子樹都返回了非空結(jié)果，則說明 ( p ) 和 ( q ) 分別位于當(dāng)前節(jié)點(diǎn)的左右兩側(cè)，所以當(dāng)前節(jié)點(diǎn)就是 LCA。
• 如果左子樹或右子樹返回了空結(jié)果，而另一個(gè)子樹返回了非空結(jié)果，則返回非空結(jié)果。

迭代方法:

• 使用棧來模擬遞歸過程，同時(shí)需要額外的空間來記錄每個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)。
• 通過回溯到根節(jié)點(diǎn)的方式，找出 ( p ) 和 ( q ) 的路徑，然后比較這兩條路徑找到最后一個(gè)相同的節(jié)點(diǎn)，這個(gè)節(jié)點(diǎn)就是 LCA。

在實(shí)現(xiàn)這類算法時(shí)，需要考慮各種邊界條件，比如當(dāng) ( p ) 或 ( q ) 之一不存在于樹中時(shí)如何處理等。通常情況下，算法設(shè)計(jì)時(shí)會假設(shè) ( p ) 和 ( q ) 都存在于樹中。如果需要處理這種情況，可以在遍歷過程中檢查是否已經(jīng)找到了兩個(gè)節(jié)點(diǎn)。

案例展示

接下來我將提供一些具體的代碼實(shí)現(xiàn)示例，以便你更好地理解如何在二叉樹中查找最近公共祖先（LCA）。我們將分別展示二叉搜索樹（BST）和一般二叉樹中查找LCA的Python代碼實(shí)現(xiàn)。

二叉搜索樹（BST）中查找LCA

class TreeNode:def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = rightdef lowestCommonAncestor(root, p, q):while root:if root.val > p.val and root.val > q.val: # 如果 p 和 q 都小于當(dāng)前節(jié)點(diǎn)，向左子樹移動root = root.leftelif root.val < p.val and root.val < q.val: # 如果 p 和 q 都大于當(dāng)前節(jié)點(diǎn)，向右子樹移動root = root.rightelse: # 當(dāng)前節(jié)點(diǎn)就是 LCAreturn root

一般二叉樹中查找LCA

class Solution:def lowestCommonAncestor(self, root, p, q):self.p_found = Falseself.q_found = Falseresult = self._helper(root, p, q)# 確保 p 和 q 都存在二叉樹中if not self.p_found or not self.q_found:return Nonereturn resultdef _helper(self, node, p, q):if not node:return None# 檢查當(dāng)前節(jié)點(diǎn)是不是 p 或 qif node == p:self.p_found = Truereturn nodeif node == q:self.q_found = Truereturn nodeleft = self._helper(node.left, p, q)right = self._helper(node.right, p, q)# 如果 p 和 q 分別在左右子樹中，那么當(dāng)前節(jié)點(diǎn)就是 LCAif left and right:return node# 否則返回找到的節(jié)點(diǎn)（left 或 right）return left or right

在上述代碼中，TreeNode 類用于定義二叉樹的節(jié)點(diǎn)，而 lowestCommonAncestor 函數(shù)實(shí)現(xiàn)了LCA的查找邏輯。在一般二叉樹的實(shí)現(xiàn)中，我們使用了一個(gè)輔助函數(shù) _helper 來遞歸地查找 p 和 q，并使用布爾變量 p_found 和 q_found 來追蹤是否已經(jīng)找到了這兩個(gè)節(jié)點(diǎn)。

希望這些代碼示例能幫助你理解如何在二叉樹中實(shí)現(xiàn)LCA的查找。如果有任何疑問或需要進(jìn)一步的解釋，請隨時(shí)提問！

在上一部分中，我們討論了二叉樹中查找最近公共祖先（LCA）的基本算法和代碼實(shí)現(xiàn)。現(xiàn)在，讓我們深入探討一些高級主題和優(yōu)化技巧，以提高算法效率和代碼可讀性。

1. 使用哈希表存儲父節(jié)點(diǎn)信息

在一般二叉樹中，如果我們能夠預(yù)先構(gòu)建一個(gè)哈希表來存儲每個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)信息，那么查找LCA的過程可以更加直觀和高效。這種方法特別適用于需要頻繁查詢LCA的場景。

def build_parent_map(root, parent_map):stack = [(root, None)]while stack:node, parent = stack.pop()parent_map[node] = parentif node.left:stack.append((node.left, node))if node.right:stack.append((node.right, node))def find_path(parent_map, target, path):while target:path.append(target)target = parent_map[target]def lowestCommonAncestor(root, p, q):parent_map = {}build_parent_map(root, parent_map)path_p = []path_q = []find_path(parent_map, p, path_p)find_path(parent_map, q, path_q)i = 0while i < len(path_p) and i < len(path_q) and path_p[i] == path_q[i]:i += 1return path_p[i-1]

這段代碼首先構(gòu)建了一個(gè)哈希表 parent_map 來存儲每個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)，然后分別找到 p 和 q 到根節(jié)點(diǎn)的路徑，并找到這兩條路徑上的最后一個(gè)相同節(jié)點(diǎn)，即為 LCA。

2. 處理多個(gè)查詢

當(dāng)需要處理多個(gè)LCA查詢時(shí)，預(yù)處理樹的信息（如父節(jié)點(diǎn)、深度等）可以顯著提升性能。例如，使用動態(tài)規(guī)劃技術(shù)可以計(jì)算出每個(gè)節(jié)點(diǎn)的深度以及每個(gè)節(jié)點(diǎn)的(2^i)倍的祖先節(jié)點(diǎn)，這樣在查詢時(shí)可以快速跳過多個(gè)層級。

3. 異常處理

在實(shí)際應(yīng)用中，應(yīng)考慮各種可能的異常情況，例如：

• 如果 p 或 q 中的一個(gè)或兩個(gè)不在樹中，應(yīng)如何處理？
• 如何處理 p 和 q 相同的情況？

在代碼實(shí)現(xiàn)中，可以通過添加適當(dāng)?shù)倪吔鐧z查來處理這些情況，確保算法的健壯性和正確性。

結(jié)論

查找二叉樹中的最近公共祖先是一個(gè)經(jīng)典問題，不僅在算法競賽中常見，也是許多實(shí)際應(yīng)用的基礎(chǔ)。通過理解不同類型的二叉樹和優(yōu)化策略，你可以更有效地解決這一問題，并將其應(yīng)用于更廣泛的場景中。希望上述內(nèi)容對你有所幫助！如果有任何疑問或需要進(jìn)一步討論的地方，歡迎隨時(shí)提問。

😍😍 大量H5小游戲、微信小游戲、抖音小游戲源碼😍😍 😍😍試玩地址： https://www.bojiogame.sg😍😍 😍看上哪一款，需要源碼的csdn私信我😍

————————————————

?最后我們放松一下眼睛