劍指 Offer 68 - II. 二叉樹(shù)的最近公共祖先
給定一個(gè)二叉樹(shù), 找到該樹(shù)中兩個(gè)指定節(jié)點(diǎn)的最近公共祖先。
百度百科中最近公共祖先的定義為：“對(duì)于有根樹(shù) T 的兩個(gè)結(jié)點(diǎn) p、q，最近公共祖先表示為一個(gè)結(jié)點(diǎn) x，滿足 x 是 p、q 的祖先且 x 的深度盡可能大（一個(gè)節(jié)點(diǎn)也可以是它自己的祖先）。”
例如，給定如下二叉樹(shù):? 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é)點(diǎn) 5 和節(jié)點(diǎn) 1 的最近公共祖先是節(jié)點(diǎn) 3。
示例 2:
輸入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
輸出: 5
解釋: 節(jié)點(diǎn) 5 和節(jié)點(diǎn) 4 的最近公共祖先是節(jié)點(diǎn) 5。因?yàn)楦鶕?jù)定義最近公共祖先節(jié)點(diǎn)可以為節(jié)點(diǎn)本身。
題目解析
root 為 p 和 q 最近公共祖先的滿足條件：
?????1. root 為 p,q 的?某公共祖先；
?????2. root.left 和 root.right 都不是 p,q 的?公共祖先；
????????????????
?root 為 p 和 q 最近公共祖先的分情況分析：
??????1. p 和 q 分別在 root 的?異側(cè)子樹(shù)（左子樹(shù)?和?右子樹(shù)）；
???????2. p = root，同時(shí)，q 在 root 的左或右子樹(shù)；
???????3. q = root，同時(shí)，p 在 root 的左或右子樹(shù)；
題目解答
思路：
? ? # step 1：判斷三種情況：
? ? #? ?1. not root：到達(dá) 葉子節(jié)點(diǎn)；
? ? #? ?2. root==p or root==q ：找到 對(duì)應(yīng)節(jié)點(diǎn)
? ? # step 2：分別 向 左右子樹(shù) 遞歸
? ? # step 3：root 的左 / 右子樹(shù)中都不包含 p,q
? ? # step 4：p，q 都不在 root 的 左子樹(shù)上，右子樹(shù) 分兩種情況：
? ? #? ?1. p/q 在 root 右子樹(shù) 中，此時(shí)返回 right 指向 p/q；
? ? #? ?2. p，q 都在 root 右子樹(shù)中，此時(shí) right 指向 最近公共祖先節(jié)點(diǎn)
? ? # step 5: 也 step 4 雷同
? ? # step 6：當(dāng) left 和 right 都不為空，說(shuō)明 p 和 q 在 root 的 異側(cè)（分別在 左右
代碼展示
# 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:'''思路：遞歸法介紹：root 為 p 和 q 最近公共祖先的滿足條件：1. root 為 p,q 的 某公共祖先；2. root.left 和 root.right 都不是 p,q 的 公共祖先；root 為 p 和 q 最近公共祖先的分情況分析：1. p 和 q 分別在 root 的 異側(cè)子樹(shù)（左子樹(shù) 和 右子樹(shù)）；2. p = root，同時(shí)，q 在 root 的左或右子樹(shù)；3. q = root，同時(shí)，p 在 root 的左或右子樹(shù)；思路：# step 1：判斷三種情況：# 1. not root：到達(dá) 葉子節(jié)點(diǎn)；# 2. root==p or root==q ：找到 對(duì)應(yīng)節(jié)點(diǎn)# step 2：分別 向 左右子樹(shù) 遞歸# step 3：root 的左 / 右子樹(shù)中都不包含 p,q# step 4：p，q 都不在 root 的 左子樹(shù)上，右子樹(shù) 分兩種情況：# 1. p/q 在 root 右子樹(shù) 中，此時(shí)返回 right 指向 p/q；# 2. p，q 都在 root 右子樹(shù)中，此時(shí) right 指向 最近公共祖先節(jié)點(diǎn)# step 5: 也 step 4 雷同# step 6：當(dāng) left 和 right 都不為空，說(shuō)明 p 和 q 在 root 的 異側(cè)（分別在 左右子樹(shù)），故 root 為最近公共祖先'''# step 1：判斷三種情況：# 1. not root：到達(dá) 葉子節(jié)點(diǎn)；# 2. root==p or root==q ：找到 對(duì)應(yīng)節(jié)點(diǎn)if not root or root==p or root==q:return root# step 2：分別 向 左右子樹(shù) 遞歸left = self.lowestCommonAncestor(root.left,p,q)right=self.lowestCommonAncestor(root.right,p,q)# step 3：root 的左 / 右子樹(shù)中都不包含 p,qif not left and not right:return None# step 4：p，q 都不在 root 的 左子樹(shù)上，右子樹(shù) 分兩種情況：# 1. p/q 在 root 右子樹(shù) 中，此時(shí)返回 right 指向 p/q；# 2. p，q 都在 root 右子樹(shù)中，此時(shí) right 指向 最近公共祖先節(jié)點(diǎn)if left and not right:return left# step 5: 也 step 4 雷同elif right and not left:return right# step 6：當(dāng) left 和 right 都不為空，說(shuō)明 p 和 q 在 root 的 異側(cè)（分別在 左右子樹(shù)），故 root 為最近公共祖先else:return root
復(fù)雜度計(jì)算
?時(shí)間復(fù)雜度：O(N)，其中 N 是二叉樹(shù)的節(jié)點(diǎn)數(shù)。二叉樹(shù)的所有節(jié)點(diǎn)有且只會(huì)被訪問(wèn)一次，因此時(shí)間復(fù)雜度為 O(N)。
-空間復(fù)雜度：O(N)，其中 N 是二叉樹(shù)的節(jié)點(diǎn)數(shù)。遞歸調(diào)用的棧深度取決于二叉樹(shù)的高度，二叉樹(shù)最壞情況下為一條鏈，此時(shí)高度為 N，因此空間復(fù)雜度為 O(N)。
運(yùn)行結(jié)果
