Lowest Common Ancestor of a Binary Search Tree

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

4种情况。

1. Both nodes are to the left of the tree.
2. Both nodes are to the right of the tree.
3. One node is on the left while the other is on the right.
4. When the current node equals to either of the two nodes, this node must be the LCA too.

1 Node *LCA(Node *root, Node *p, Node *q) {
2   if (!root || !p || !q) return NULL;
3   if (max(p->data, q->data) < root->data)
4     return LCA(root->left, p, q);
5   else if (min(p->data, q->data) > root->data)
6     return LCA(root->right, p, q);
7   else
8     return root;
9 }

http://leetcode.com/2011/07/lowest-common-ancestor-of-a-binary-search-tree.html

Lowest Common Ancestor of a Binary Search Tree,布布扣,bubuko.com

Lowest Common Ancestor of a Binary Search Tree

原文：http://www.cnblogs.com/longhorn/p/3606704.html