Skip to content

236 lowest common ancestor of a binary tree

236. Lowest Common Ancestor of a Binary Tree

题目: https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/

难度:

Medium

思路

求root到node的path，然后对比path，最后一个想同的点就是lowest common ancestor

好开心，AC了

但是我根本不能在Runtime Distribution 上找到我，因为太慢了||||


class Solution(object):
    def lowestCommonAncestor(self, root, p, q):
        """
        :type root: TreeNode
        :type p: TreeNode
        :type q: TreeNode
        :rtype: TreeNode
        """
        pathP = self.pathTo(root,p)
        pathQ = self.pathTo(root,q)
        n = min(len(pathP), len(pathQ))

        ans = root
        for i in range(n):
            if pathP[i] == pathQ[i]:
                ans = pathP[i]
            else:
                break
        return ans


    def pathTo(self, root, goal):
        # goal node ,path
        if root == None: return root
        stack = [(root, [root])]
        while stack:
            node, path = stack.pop()
            if node == goal:
                return path
            if node.left: stack.append((node.left, path + [node.left]))
            if node.right: stack.append((node.right, path + [node.right]))

递归解法，之所以我没有用递归因为有疑惑, BASE CASE 很容易想到，root 是none，或者p == root 或者q == root,那么LCA就是root，如果两个node一个在左边，一个在右边，那么LCA也是root，但是如果一个是6，另一个是4则有一点疑惑，但其实是没有问题的，因为这个时候给的总是他们的共同root，所以这个递归解法是没错的，总是想到递归是在那个状况下递归

        _______3______
       /              \
    ___5__          ___1__
   /      \        /      \
   6      _2       0       8
         /  \
         7   4

AC代码

class Solution(object):
    def lowestCommonAncestor(self, root, p, q):
        """
        :type root: TreeNode
        :type p: TreeNode
        :type q: TreeNode
        :rtype: TreeNode
        """
        if root == None:
            return None

        if p == root or q == root:
            return root

        left = self.lowestCommonAncestor(self.left,p,q)
        right = self.lowestCommonAncestor(self.right,p,q)

        if left and right:
            return root

        return left if left is None else right
回到顶部