给出python二叉树两个点该如何求出其最小共同父节点-创新互联-成都创新互联网站建设

关于创新互联

多方位宣传企业产品与服务 突出企业形象

公司简介 公司的服务 荣誉资质 新闻动态 联系我们

给出python二叉树两个点该如何求出其最小共同父节点-创新互联

本篇文章给大家分享的是有关给出python二叉树两个点该如何求出其最小共同父节点,小编觉得挺实用的,因此分享给大家学习,希望大家阅读完这篇文章后可以有所收获,话不多说,跟着小编一起来看看吧。

十多年的兴安网站建设经验,针对设计、前端、开发、售后、文案、推广等六对一服务,响应快,48小时及时工作处理。全网整合营销推广的优势是能够根据用户设备显示端的尺寸不同,自动调整兴安建站的显示方式,使网站能够适用不同显示终端,在浏览器中调整网站的宽度,无论在任何一种浏览器上浏览网站,都能展现优雅布局与设计,从而大程度地提升浏览体验。成都创新互联从事“兴安网站设计”,“兴安网站推广”以来,每个客户项目都认真落实执行。

题目是在给出二叉树中两个点p,q,求出其最小共同父节点(LCA Lowest Common Ancestor),如下图很好理解,比如5和1的共同父节点是3;6和7的最小共同父节点是5;而5和4的最小共同父节点是5本身。 给出python二叉树两个点该如何求出其最小共同父节点

考虑了一下,其实思路很简答,首先用前序或者层级遍历二叉树得出节点队列,因为前序和层级都是先遍历父节点再子节点,这样队列后的节点的父节点一定存在队列中。然后从后往前反序遍历这个节点队列,如果是给出p, q这两个中的父节点,则替换为其父节点,如果p和q是同一个节点,就是其最小共同父节点。

代码如下,使用层级遍历,遍历的时候判断是否已经读取p,q;如果都读取了停止遍历,避免读取不必要数据。

# 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二叉树两个点该如何求出其最小共同父节点,小编相信有部分知识点可能是我们日常工作会见到或用到的。希望你能通过这篇文章学到更多知识。更多详情敬请关注创新互联-成都网站建设公司行业资讯频道。


文章标题:给出python二叉树两个点该如何求出其最小共同父节点-创新互联
URL网址:http://kswsj.cn/article/dsjgoo.html

其他资讯