python--lintcode88. 最近の公的祖先

2つのノードの最も近い共通の親ノード(LCA)を見つけるには、2本のツリーを指定します.
最近の共通祖先は、2つのノードの共通の祖先ノードであり、最大の深さを有する.
注意事項
与えられた2つのノードがツリーに存在すると仮定します.
サンプル
下の二叉木に対して

  4
 / \
3   7
   / \
  5   6

LCA(3, 5) =  4
LCA(5, 6) =  7
LCA(6, 7) =  7
LCA(最近のパブリック親ノード)問題は二叉木に古典的な問題で、木の構造にparentポインタがあればこの問題は簡単ですが、なければ考えなければなりません.
依然として分治法の思想を用いて、考えてみて、もし1つの木の結点に対して、左の子の木の中でAを見つけて、右の子の木の中でBを見つけて、それはこの結点が公共のノードであることを説明します
詳細はコード注釈に書かれています.

class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left, self.right = None, None


class Solution:
    """
       @param: root: The root of the binary search tree.
       @param: A: A TreeNode in a Binary.
       @param: B: A TreeNode in a Binary.
       @return: Return the least common ancestor(LCA) of the two nodes.
       """

    def lowestCommonAncestor(self, root, A, B):
        # A&B=>LCA
        # !A&!B=>None
        # A&!B=>A
        # B&!A=>B
        if(root is None or root==A or root==B):
            return root        # root    root A  root B，     A B    
        left=self.lowestCommonAncestor(root.left,A,B)
        right=self.lowestCommonAncestor(root.right,A,B)
        if(left is not None and right is not None):
            return root      #       A，      B，     root      
        if(left is None):    #     none     ，        A B
            return right
        if(right is None):   #  
            return left
        return None



a=Tree = TreeNode(2)
b=Tree.left = TreeNode(1)
c=Tree.right = TreeNode(3)
d=b.left=TreeNode(4)
s = Solution()
print(s.lowestCommonAncestor(a,b,d).val)