要求

• 给定一棵二分搜索树和两个节点，寻找这两个节点的最近公共祖先

示例

• 2和8的最近公共祖先是6
• 2和4的最近公共祖先是2

思路

• p q<node
• node<p q
• p<=node<=q

实现

1 class Solution {
2 public:
3 TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
4
5 assert( p != NULL && q != NULL );
6
7 if( root == NULL )
8 return NULL;
9
10 if( p->val < root->val && q->val < root->val )
11 return lowestCommanAncestor( root->left , p , q );
12 if( p->val > root->val && q->val > root->val )
13 return lowestCommanAncestor( root->right , p , q );
14
15 return root;
16 }
17 };

相关

• 98 Validate Binary Search Tree
• 450 Delete Node in a BST
• 108 Convert Sorted Array to Binary Search Tree
• 230 Kth Smallest Element in a BST
• 236 Lowest Common Ancestor of a Binary Tree