# Lowest Common Ancestor of a Binary Search Tree

## 问题描述

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

According to thedefinition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allowa node to be a descendant of itself).”

`        _______6______       /              \    ___2__          ___8__   /      \        /      \   0      _4       7       9         /  \         3   5`

For example, the lowest common ancestor (LCA) of nodes`2`and`8`is`6`. Another example is LCA of nodes`2`and`4`is`2`, since a node can be a descendant of itself according to the LCA definition.

## Python

`# Definition for a binary tree node.# class TreeNode(object):#     def __init__(self, x):#         self.val = x#         self.left = None#         self.right = None​class Solution(object):    def lowestCommonAncestor(self, root, p, q):        """        :type root: TreeNode        :type p: TreeNode        :type q: TreeNode        :rtype: TreeNode        """        if p.val > q.val:            p, q = q, p        while root.val < p.val or root.val > q.val:            if root.val > q.val:                root = root.left                continue            if root.val < p.val:                root = root.right                continue            if root.val == p.val:                return root            if root.val == q.val:                return root        return root`

## Java

`class Solution {    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {        if (p.val > q.val) {            TreeNode tmp = p;            p = q;            q = tmp;        }        while (root.val < p.val || root.val > q.val) {            if (root.val < p.val) {                root = root.right;            }            if (root.val > q.val) {                root = root.left;            }        }        return root;    }}`

# Golang

`func lowestCommonAncestor(root *TreeNode, p *TreeNode, q *TreeNode) *TreeNode{  if p.Val > q.Val {    p, q = q, p  }​  for root.Val < p.Val || root.Val > q.Val {    if root.Val < p.Val {      root = root.Right    }    if root.Val > q.Val {      root = root.Left    }  }  return root}`