給出python二叉樹(shù)兩個(gè)點(diǎn)該如何求出其最小共同父節(jié)點(diǎn)

本篇文章給大家分享的是有關(guān)給出python二叉樹(shù)兩個(gè)點(diǎn)該如何求出其最小共同父節(jié)點(diǎn)，小編覺(jué)得挺實(shí)用的，因此分享給大家學(xué)習(xí)，希望大家閱讀完這篇文章后可以有所收獲，話不多說(shuō)，跟著小編一起來(lái)看看吧。

創(chuàng)新互聯(lián)建站是一家專注于做網(wǎng)站、成都網(wǎng)站設(shè)計(jì)與策劃設(shè)計(jì),撫松網(wǎng)站建設(shè)哪家好?創(chuàng)新互聯(lián)建站做網(wǎng)站,專注于網(wǎng)站建設(shè)十余年,網(wǎng)設(shè)計(jì)領(lǐng)域的專業(yè)建站公司;建站業(yè)務(wù)涵蓋:撫松等地區(qū)。撫松做網(wǎng)站價(jià)格咨詢:028-86922220

題目是在給出二叉樹(shù)中兩個(gè)點(diǎn)p，q，求出其最小共同父節(jié)點(diǎn)（LCA Lowest Common Ancestor)，如下圖很好理解，比如5和1的共同父節(jié)點(diǎn)是3；6和7的最小共同父節(jié)點(diǎn)是5；而5和4的最小共同父節(jié)點(diǎn)是5本身。

考慮了一下，其實(shí)思路很簡(jiǎn)答，首先用前序或者層級(jí)遍歷二叉樹(shù)得出節(jié)點(diǎn)隊(duì)列，因?yàn)榍靶蚝蛯蛹?jí)都是先遍歷父節(jié)點(diǎn)再子節(jié)點(diǎn)，這樣隊(duì)列后的節(jié)點(diǎn)的父節(jié)點(diǎn)一定存在隊(duì)列中。然后從后往前反序遍歷這個(gè)節(jié)點(diǎn)隊(duì)列，如果是給出p, q這兩個(gè)中的父節(jié)點(diǎn)，則替換為其父節(jié)點(diǎn)，如果p和q是同一個(gè)節(jié)點(diǎn)，就是其最小共同父節(jié)點(diǎn)。

代碼如下，使用層級(jí)遍歷，遍歷的時(shí)候判斷是否已經(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二叉樹(shù)兩個(gè)點(diǎn)該如何求出其最小共同父節(jié)點(diǎn)，小編相信有部分知識(shí)點(diǎn)可能是我們?nèi)粘９ぷ鲿?huì)見(jiàn)到或用到的。希望你能通過(guò)這篇文章學(xué)到更多知識(shí)。更多詳情敬請(qǐng)關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道。

標(biāo)題名稱：給出python二叉樹(shù)兩個(gè)點(diǎn)該如何求出其最小共同父節(jié)點(diǎn)
分享地址：http://muchs.cn/article6/pihjig.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供手機(jī)網(wǎng)站建設(shè)、、搜索引擎優(yōu)化、虛擬主機(jī)、用戶體驗(yàn)、小程序開(kāi)發(fā)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)