資訊專欄INFORMATION COLUMN
摘要：給定一個(gè)二叉搜索樹(shù)找到該樹(shù)中兩個(gè)指定節(jié)點(diǎn)的最近公共祖先。示例輸入輸出解釋節(jié)點(diǎn)和節(jié)點(diǎn)的最近公共祖先是因?yàn)楦鶕?jù)定義最近公共祖先節(jié)點(diǎn)可以為節(jié)點(diǎn)本身。這意味著二叉搜索樹(shù)所有的元素可以用某種統(tǒng)一的方式排序。
給定一個(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)也可以是它自己的祖先）?！?/p>
例如，給定如下二叉搜索樹(shù): 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é)點(diǎn) 2 和節(jié)點(diǎn) 8 的最近公共祖先是 6。
示例 2:輸入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
輸出: 2
解釋: 節(jié)點(diǎn) 2 和節(jié)點(diǎn) 4 的最近公共祖先是 2, 因?yàn)楦鶕?jù)定義最近公共祖先節(jié)點(diǎn)可以為節(jié)點(diǎn)本身。
說(shuō)明:思路：所有節(jié)點(diǎn)的值都是唯一的。
p、q 為不同節(jié)點(diǎn)且均存在于給定的二叉搜索樹(shù)中。
二叉搜索樹(shù)的定義為：對(duì)于樹(shù)中的每個(gè)節(jié)點(diǎn)X，它的左子樹(shù)的所有關(guān)鍵字值小于X的關(guān)鍵字值，而它的右子樹(shù)中所有關(guān)鍵字值大于X的關(guān)鍵字值。這意味著二叉搜索樹(shù)所有的元素可以用某種統(tǒng)一的方式排序。 在這里只需要比較兩個(gè)節(jié)點(diǎn)和根的值的大小，確定兩個(gè)節(jié)點(diǎn)所在位置，如果兩個(gè)節(jié)點(diǎn)分別在根的兩邊，那么可以肯定它們的最近公共祖先就是根節(jié)點(diǎn)，如果在同一側(cè)就可以遞歸查找了。
遞歸寫法：
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def lowestCommonAncestor(self, root: "TreeNode", p: "TreeNode", q: "TreeNode") -> "TreeNode":
if p.val > root.val < q.val:
return self.lowestCommonAncestor(root.right, p, q)
elif p.val < root.val > q.val:
return self.lowestCommonAncestor(root.left, p, q)
else:
return root
非遞歸寫法：
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def lowestCommonAncestor(self, root: "TreeNode", p: "TreeNode", q: "TreeNode") -> "TreeNode":
while root:
if p.val > root.val < q.val:
root = root.right
elif p.val < root.val > q.val:
root = root.left
else:
return root
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://www.ezyhdfw.cn/yun/43832.html
摘要：寫在最前面導(dǎo)師貪腐出逃美國(guó)，兩年未歸，可憐了我。拿了小米和美團(tuán)的，要被延期，失效，工作重新找。把準(zhǔn)備過(guò)程紀(jì)錄下來(lái)，共勉。 寫在最前面 導(dǎo)師貪腐出逃美國(guó)，兩年未歸，可憐了我。拿了小米和美團(tuán)的offer，要被延期，offer失效，工作重新找。把準(zhǔn)備過(guò)程紀(jì)錄下來(lái)，共勉。 二叉樹(shù)的基礎(chǔ) 結(jié)點(diǎn)定義 public class TreeNode{ int val; TreeNode ...
摘要：算法前端發(fā)展的再快，也不要忘記精進(jìn)自己的算法，算法是靈魂和核心。我會(huì)把我刷過(guò)的算法題總結(jié)歸類，不斷完善。 算法 前端發(fā)展的再快，也不要忘記精進(jìn)自己的算法，算法是靈魂和核心。我會(huì)把我刷過(guò)的算法題總結(jié)歸類，不斷完善。歡迎大家關(guān)注。 數(shù)組和堆棧 數(shù)組去重 旋轉(zhuǎn)數(shù)組 如何快速找出兩個(gè)數(shù)之和等于某一個(gè)值的兩個(gè)數(shù)？ 快排 排序算法大總結(jié) 快速找到數(shù)組中的最大值 多維數(shù)組的展開(kāi) 二分查找 有效的括...
摘要：后面也寫了幾種常見(jiàn)的排序算法，并用快排求第大值，另外如果之前版的作者看到的話可以留言，我會(huì)標(biāo)明文章引用。 之前實(shí)習(xí)筆試的時(shí)候刷題一直用的java，也參考某篇文章寫過(guò)java版的二叉樹(shù)常見(jiàn)算法，因?yàn)轳R上要轉(zhuǎn)正面試了，這幾天都在準(zhǔn)備面試，就把之前的翻出來(lái)用javascript重新寫了一遍，二叉樹(shù)基本都是遞歸處理的，也比較簡(jiǎn)單，就當(dāng)做熱身。后面也寫了幾種常見(jiàn)的排序算法，并用快排求第K大值，另...
閱讀 3639·2021-09-22 15:02
閱讀 3993·2021-09-02 15:21
閱讀 2341·2019-08-30 15:55
閱讀 2933·2019-08-30 15:44
閱讀 923·2019-08-29 16:56
閱讀 2560·2019-08-23 18:22
閱讀 3480·2019-08-23 12:20
閱讀 3228·2019-08-23 11:28
