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

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

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

考虑了一下，其实思路很简答，首先用前序或者层级遍历二叉树得出节点队列，因为前序和层级都是先遍历父节点再子节点，这样队列后的节点的父节点一定存在队列中。然后从后往前反序遍历这个节点队列，如果是给出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 = Noneclass 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二叉树两个点该如何求出其最小共同父节点，小编相信有部分知识点可能是我们日常工作会见到或用到的。希望你能通过这篇文章学到更多知识。更多详情敬请关注行业资讯频道。