题目:
Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.
给出一个二叉搜索树,求出给定了两个节点的最小公共祖先-
分析:
- 对于一棵二叉搜索树来说,两个节点的公共祖先肯定是大于等于其中一个节点,小于等于另外一个节点的
- 根据二叉搜索树的特性,在递归的过程中,如果当前节点值大于两个给定节点的话,那么下一步递归将要递归左节点,如果当前节点值小雨两个给定节点的话,那么下一步递归将要递归右节点
代码:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (root->val > p->val && root->val > q->val) {
return lowestCommonAncestor(root->left, p, q);
} else if (root->val < p->val && root->val < q->val) {
return lowestCommonAncestor(root->right, p, q);
} else {
return root;
}
}