python技术面试题(二十一)

小闫同学啊

发布于 2019-07-18 15:37:29

5810

发布于 2019-07-18 15:37:29

文章被收录于专栏：小闫笔记小闫笔记

正文共：837 字 5 图预计阅读时间：3 分钟

每日分享

If you want to awaken all of humanity, awaken all of yourself.

--老子

小闫语录：

有人说此句是老子『西升经』中一语，有人说此句出自『化胡经』。翻译简单，意译难，没有具体的上下文，还是不翻译此句了。

排序二叉树如何查找两个叶节点的最近公共祖先

排序二叉树有一个特点，就是左子树的节点都比父节点小，位于右子树的节点都比父节点大。抓住这个特点，我们从根节点开始进行比较查找。如果当前节点的值比两个节点的值都大，那么最低的公共祖先节点一定在该节点的左子树中，下一步就开始遍历当前节点的左子树。如果当前节点的值比两个节点的值都小，那么最低的公共祖先节点一定在该节点的右子树中，下一步就是遍历当前节点的右子树。这样从上到下找到第一个在两个输入节点的值之间的节点。

了解完之后，我们利用python代码实现一下：

class TreeNode(object):
    def __init__(self,item):
        self.item = item
        self.lchild = None
        self.rchild = None
    def getCommonAncestor(root,node1,node2):
        while root:
            if root.item > node1.item and root.item > node2.item:
                root = root.lchild
            elif root.item < node1.item and root.item < node2.item:
                root = root.rchild
            else:
                return root
        return None