剑指offer 68-I 二叉搜索树的最近公共祖先

题目链接

题意

如标题。附一棵二叉搜索树的图

题解

由于这题是二叉搜索树，且各节点的值唯一。
那么就可以按照从上往下找的思路，然后根据两结点找到其公共祖先节点的所有可能的情况进行判断：

• p 和 q 在 root 的子树中，且分列 root 的 异侧（即分别在左、右子树中）；
• p=root，且 q 在 root 的左或右子树中；
• q=root，且 p 在 root 的左或右子树中；

具体地说，除了这三种情况，其余情况不断移动根节点；当遇到上述三种情况时，则结束查找。

代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        while (root != NULL) {
            //这一行代表着找到公共祖先的三种情形，小于表示分列两侧，等于表示两个节点中有一个为公共祖先
            if ((root->val - p->val)*(root->val - q->val) <= 0) break;
            else if ((root->val - p->val) > 0) {
                root = root->left;
            } else {
                root = root->right;
            }
        }
        return root;
    }
};