236. Lowest Common Ancestor of a Binary Tree

Loading...LeetCode

分情况讨论后就容易看出是 recursive traversal:

1. each of p, q in one subtree -> root is the LCA

2. p, q in one subtree:

   • p, q in one continuously line -> case 3

   • p, q in separate subtrees -> case 1

3. p/q is the root: root is the LCA

If the current (sub)tree contains both p and q, then the function result is their LCA. If only one of them is in that subtree, then the result is that one of them. If neither are in that subtree, the result is None.

其实就是找到p, q 的任何一个就返回它，如果有某个节点的左右子节点分别返回p, q ，那说明它肯定就是LCA，如果一直没有这个节点，那说明LCA就是p, q 中的一个，那按照这个规则返回到根节点就行。

bottom-up

# 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':
        # 1. each of p, q in one subtree -> root is the LCA
        # 2. p, q in one subtree
        ## 2.1 p, q in one continuously line -> 3 -> certain root returned
        ## 2.2 p, q in separate subtrees -> 1 -> certain root returned
        # 3. p/q is the root: root is the LCA
        if not root or root == q or root == p:
            return root
        # 3 solved, only 1 or 2 now
        l = self.lowestCommonAncestor(root.left, p, q)
        r = self.lowestCommonAncestor(root.right, p, q)
        if l and r: # case 1
            return root
        else:
            return l if l else r