> For the complete documentation index, see [llms.txt](https://liuxue2010.gitbook.io/data-structure-and-algorithms/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://liuxue2010.gitbook.io/data-structure-and-algorithms/binary-tree-and-divide-conquer/lowest-common-ancestor.md).

# Lowest Common Ancestor

Given the root and two nodes in a Binary Tree. Find the lowest common ancestor(LCA) of the two nodes.

The lowest common ancestor is the node with largest depth which is the ancestor of both nodes.

## Example

For the following binary tree:

```
  4
 / \
3   7
   / \
  5   6
```

LCA(3, 5) = 4

LCA(5, 6) = 7

LCA(6, 7) = 7

## Solution

分治算法分治之前的代码是上一个递归的延伸，就是结束条件。

分治算法后面的就是关系的构成，最终返回结构。

```
"""
Definition of TreeNode:
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 and B: two nodes in a Binary.
    @return: Return the least common ancestor(LCA) of the two nodes.
    """ 
    def lowestCommonAncestor(self, root, A, B):
        if root == None:
            return None
        if root == A or root == B: #stop机制, 从上一个递归是root.left or root.right 进来的，这样无论是等于左右节点，都退出返回。 
            return root
        left = self.lowestCommonAncestor(root.left, A, B)
        right = self.lowestCommonAncestor(root.right, A, B)

        if left and right:
            return root
        if left:
            return left
        if right:
            return right
        return None
```