資訊專欄INFORMATION COLUMN
摘要：給定一個二叉搜索樹找到該樹中兩個指定節(jié)點的最近公共祖先。示例輸入輸出解釋節(jié)點和節(jié)點的最近公共祖先是因為根據(jù)定義最近公共祖先節(jié)點可以為節(jié)點本身。這意味著二叉搜索樹所有的元素可以用某種統(tǒng)一的方式排序。
給定一個二叉搜索樹, 找到該樹中兩個指定節(jié)點的最近公共祖先。百度百科中最近公共祖先的定義為：“對于有根樹 T 的兩個結(jié)點 p、q，最近公共祖先表示為一個結(jié)點 x，滿足 x 是 p、q 的祖先且 x 的深度盡可能大（一個節(jié)點也可以是它自己的祖先）?！?/p>
例如，給定如下二叉搜索樹: 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é)點且均存在于給定的二叉搜索樹中。
二叉搜索樹的定義為：對于樹中的每個節(jié)點X，它的左子樹的所有關(guān)鍵字值小于X的關(guān)鍵字值，而它的右子樹中所有關(guān)鍵字值大于X的關(guān)鍵字值。這意味著二叉搜索樹所有的元素可以用某種統(tǒng)一的方式排序。 在這里只需要比較兩個節(jié)點和根的值的大小，確定兩個節(jié)點所在位置，如果兩個節(jié)點分別在根的兩邊，那么可以肯定它們的最近公共祖先就是根節(jié)點，如果在同一側(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)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/43832.html
摘要：寫在最前面導(dǎo)師貪腐出逃美國，兩年未歸，可憐了我。拿了小米和美團的，要被延期，失效，工作重新找。把準備過程紀錄下來，共勉。 寫在最前面 導(dǎo)師貪腐出逃美國，兩年未歸，可憐了我。拿了小米和美團的offer，要被延期，offer失效，工作重新找。把準備過程紀錄下來，共勉。 二叉樹的基礎(chǔ) 結(jié)點定義 public class TreeNode{ int val; TreeNode ...
摘要：算法前端發(fā)展的再快，也不要忘記精進自己的算法，算法是靈魂和核心。我會把我刷過的算法題總結(jié)歸類，不斷完善。 算法 前端發(fā)展的再快，也不要忘記精進自己的算法，算法是靈魂和核心。我會把我刷過的算法題總結(jié)歸類，不斷完善。歡迎大家關(guān)注。 數(shù)組和堆棧 數(shù)組去重 旋轉(zhuǎn)數(shù)組 如何快速找出兩個數(shù)之和等于某一個值的兩個數(shù)？ 快排 排序算法大總結(jié) 快速找到數(shù)組中的最大值 多維數(shù)組的展開 二分查找 有效的括...
摘要：后面也寫了幾種常見的排序算法，并用快排求第大值，另外如果之前版的作者看到的話可以留言，我會標明文章引用。 之前實習(xí)筆試的時候刷題一直用的java，也參考某篇文章寫過java版的二叉樹常見算法，因為馬上要轉(zhuǎn)正面試了，這幾天都在準備面試，就把之前的翻出來用javascript重新寫了一遍，二叉樹基本都是遞歸處理的，也比較簡單，就當(dāng)做熱身。后面也寫了幾種常見的排序算法，并用快排求第K大值，另...
閱讀 3484·2021-09-22 15:02
閱讀 3536·2021-09-02 15:21
閱讀 2145·2019-08-30 15:55
閱讀 2796·2019-08-30 15:44
閱讀 794·2019-08-29 16:56
閱讀 2426·2019-08-23 18:22
閱讀 3354·2019-08-23 12:20
閱讀 3102·2019-08-23 11:28
