75. nearest common ancestor of binary search tree

subject

Given a binary search tree , Find the nearest common ancestor of the two specified nodes in the tree .

In Baidu Encyclopedia, the most recent definition of public ancestor is ：“ For a tree T Two nodes of p、q, Recently, the common ancestor is represented as a node x, Satisfy x yes p、q Our ancestors and x As deep as possible （ A node can also be its own ancestor ）.”

Ideas

iteration ：
1. Loop search ： When node root Jump out when empty ;

• When p, q All in root Of Right subtree in , Then traverse to root.right ;
• otherwise , When p, q All in root Of In the left subtree , Then traverse to root.left ;
• otherwise , It means that Recent public ancestor , Jump out of .

2. Return value ： Recent public ancestor root .

Code

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        while root:
            if root.val < p.val and root.val < q.val: # p,q  All in  root  In the right subtree 
                root = root.right #  Traverse to the right child node 
            elif root.val > p.val and root.val > q.val: # p,q  All in  root  In the left subtree 
                root = root.left #  Traverse to the left child node 
            else: break
        return root