Lowest Common Ancestor of a Binary Tree

题目描述

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

folloup up 带parent节点的情况

解题方法

方法1

对于每一个node

• 如果和p或者q相等，那么这就是LCA
• 检查p和q在它的哪一边，如果是在两边的话，这个就是LCA
• 如果在同一边的话，就往左或者往右

这个算法worst case的时间复杂度是O(n^2)

方法2

bottom-up找，直接到左右字数里找LCA，然后往上级返回，这里不断recursive其实找到就是 它们本来的两个node，如果左右都找到就说明当前node是LCA,只需要O(n)

经验总结

• 如果有多次重复的问题，那么找出每次重复之间的子问题关系，将重复的量去掉
• 树的recursive不一定要先判断当前的node，如果子树的信息对当前node有用，可以先判断子树变为bottom-up的做法
• 树的bottom-up和top-down的主要差别就是： 先处理当前节点还是先处理子树

follow up

如果带parent,最直观的是从p,q分别建造到root的路径，然后找出LCA,但是这样就需要extra space来保存路径

可以参考intersection of 2 lists, 先找出两个node depth的差距，然后让更深的那个先往上走diff步，然后再同步 往上，就可以通过O(1)的space找到LCA

Solution

方法1

O(n^2)

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

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

        left1 = self.find(root.left, p)
        left2 = self.find(root.left, q)

        if left1 and left2:
            return self.lowestCommonAncestor(root.left, p, q)
        if not left1 and not left2:
            return self.lowestCommonAncestor(root.right, p, q)

        return root

    def find(self, root, node):
        if not root:
            return False
        if root == node:
            return True

        leftFind = False
        rightFind = False
        if root.left:
            leftFind = self.find(root.left, node)
        if root.right:
            rightFind = self.find(root.right, node)
        return leftFind or rightFind

方法2

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

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

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

        if left and right:
            return root

        return left if left else right

Reference

• LCA in Binary Tree