Tree - 235. Lowest Common Ancestor of a Binary Search Tree

235. 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 the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

Given binary search tree:  root = [6,2,8,0,4,7,9,null,null,3,5]

Example 1:

Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
Output: 6
Explanation: The LCA of nodes 2 and 8 is 6.

Example 2:

Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
Output: 2
Explanation: The LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.


Note:

- All of the nodes' values will be unique.
- p and q are different and both values will exist in the BST.

思路：

在bst中找出两个节点的最近祖先节点LCA,因为是在bst中，所以很容易得出如果pq两个节点在root两边，那么LCA一定是当前root, 如果pq都在root的左边或者右边，那么就变成左边或者右边的求解的一个递归子问题。

代码：

go：

/**

 * Definition for TreeNode.
 * type TreeNode struct {
 *     Val int
 *     Left *ListNode
 *     Right *ListNode
 * }
 */
 func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
     if root == nil || root == p || root == q {
         return root
     }
     
     if root.Val > p.Val && root.Val > q.Val {   // pq都在左子树中
         return lowestCommonAncestor(root.Left, p, q)
     } else if root.Val < p.Val && root.Val < q.Val { // pq都在右子树中
         return lowestCommonAncestor(root.Right, p, q)
     } else { // pq一个在一边，LCA一定是当前“root节点”
         return root
     }
}