本篇文章給大家分享的是有關(guān)給出python二叉樹兩個點該如何求出其最小共同父節(jié)點,小編覺得挺實用的,因此分享給大家學習,希望大家閱讀完這篇文章后可以有所收獲,話不多說,跟著小編一起來看看吧。
十多年的興安網(wǎng)站建設經(jīng)驗,針對設計、前端、開發(fā)、售后、文案、推廣等六對一服務,響應快,48小時及時工作處理。全網(wǎng)整合營銷推廣的優(yōu)勢是能夠根據(jù)用戶設備顯示端的尺寸不同,自動調(diào)整興安建站的顯示方式,使網(wǎng)站能夠適用不同顯示終端,在瀏覽器中調(diào)整網(wǎng)站的寬度,無論在任何一種瀏覽器上瀏覽網(wǎng)站,都能展現(xiàn)優(yōu)雅布局與設計,從而大程度地提升瀏覽體驗。成都創(chuàng)新互聯(lián)從事“興安網(wǎng)站設計”,“興安網(wǎng)站推廣”以來,每個客戶項目都認真落實執(zhí)行。題目是在給出二叉樹中兩個點p,q,求出其最小共同父節(jié)點(LCA Lowest Common Ancestor),如下圖很好理解,比如5和1的共同父節(jié)點是3;6和7的最小共同父節(jié)點是5;而5和4的最小共同父節(jié)點是5本身。
考慮了一下,其實思路很簡答,首先用前序或者層級遍歷二叉樹得出節(jié)點隊列,因為前序和層級都是先遍歷父節(jié)點再子節(jié)點,這樣隊列后的節(jié)點的父節(jié)點一定存在隊列中。然后從后往前反序遍歷這個節(jié)點隊列,如果是給出p, q這兩個中的父節(jié)點,則替換為其父節(jié)點,如果p和q是同一個節(jié)點,就是其最小共同父節(jié)點。
代碼如下,使用層級遍歷,遍歷的時候判斷是否已經(jīng)讀取p,q;如果都讀取了停止遍歷,避免讀取不必要數(shù)據(jù)。
# 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': preNodeList = [] checkList = [root] count = 2 while count > 0: nextList = [] for node in checkList: preNodeList.append(node) if node == p or node == q: count = count -1 if count == 0: pass if node.left != None: nextList.append(node.left) if node.right != None: nextList.append(node.right) checkList = nextList while p!= q: currentNode = preNodeList.pop() if currentNode.right == p or currentNode.left == p: p = currentNode if currentNode.right == q or currentNode.left == q: q = currentNode return p
以上就是給出python二叉樹兩個點該如何求出其最小共同父節(jié)點,小編相信有部分知識點可能是我們?nèi)粘9ぷ鲿姷交蛴玫降?。希望你能通過這篇文章學到更多知識。更多詳情敬請關(guān)注創(chuàng)新互聯(lián)-成都網(wǎng)站建設公司行業(yè)資訊頻道。
新聞標題:給出python二叉樹兩個點該如何求出其最小共同父節(jié)點-創(chuàng)新互聯(lián)
當前URL:http://www.muchs.cn/article0/dsjgoo.html
成都網(wǎng)站建設公司_創(chuàng)新互聯(lián),為您提供網(wǎng)站建設、網(wǎng)站設計、全網(wǎng)營銷推廣、網(wǎng)頁設計公司、云服務器、網(wǎng)站內(nèi)鏈
聲明:本網(wǎng)站發(fā)布的內(nèi)容(圖片、視頻和文字)以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主,如果涉及侵權(quán)請盡快告知,我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場,如需處理請聯(lián)系客服。電話:028-86922220;郵箱:631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載,或轉(zhuǎn)載時需注明來源: 創(chuàng)新互聯(lián)
猜你還喜歡下面的內(nèi)容