题目描述

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

对于该题的最近的公共祖先定义:对于有根树T的两个节点p、q，最近公共祖先LCA(T,p,q)表示一个节点x，满足x是p和q的祖先且x的深度尽可能大。在这里，一个节点也可以是它自己的祖先.

alt

示例1

  • 输入： {7,1,12,0,4,11,14,#,#,3,5},1,12
  • 返回值：7
  • 说明： 节点1 和 节点12的最近公共祖先是7

题解1：一次循环遍历

  • 由于是搜索二叉树，且给定了两个节点的数值，因此可以直接通过遍历查找到这两个节点
  1. 若当前节点值既大于p，也大于q，那么祖先节点一定在左子树上，遍历左子树
  2. 若当前节点值既小于p，也小于q，那么祖先节点一定在右子树上，遍历右子树
  3. 若当前节点值小于p且大于q，或者当前节点值小于q且大于p，那么当前节点就是祖先节点
/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @param p int整型 
     * @param q int整型 
     * @return int整型
     */
    int lowestCommonAncestor(TreeNode* root, int p, int q) {
        // write code here 
        //若当前节点值既大于p，也大于q，那么祖先节点一定在左子树上，遍历左子树
        //若当前节点值既小于p，也小于q，那么祖先节点一定在右子树上，遍历右子树
        //若当前节点值小于p且大于q，或者当前节点值小于q且大于p，那么当前节点就是祖先节点
        TreeNode * cur = root;
        //注意：这里不需要进行递归处理
        //因为该二叉搜索树是有序树，且两个节点的值已经给定了，只需要按照条件进行遍历查找即可
        while(true){
            if(cur->val > p && cur->val > q)
                cur = cur->left;//遍历左子树
            else if(cur->val < p && cur->val < q)
                cur = cur->right;//遍历右子树
            else //除开上面两种情况外，已经找到了公共祖先节点
                return cur->val;
        } 
    }
};

**题解2：使用递归,用数组保存节点的路径

思路

  • 从根节点进行查找，找到两条到给定的节点值的路径，然后反转链表，这两条路径必然会存在第一个公共节点。 剑指offer题目JZ52-两个链表的第一个公共节点就是查找第一个公共节点的问题。

步骤：

  1. 使用两个数组，保存根节点到指定节点值路径上的节点
  2. 反转两个链表，反转链表使用双指针法
  3. 查找第一个公共节点

**题解3：使用递归，用数组保存节点路径上的值

思路

  • 从根节点进行查找，找到两条到给定的节点值的路径，将路径上的值保存在数组中。
  • 因为搜索二叉树是不重复的，所以对两个路径值的数组进行遍历，找到值相等的最后那个数，就是最近的祖先节点值。

代码

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @param p int整型 
     * @param q int整型 
     * @return int整型
     */
    void findpath(TreeNode* root,vector<int> & v,int i){
        while(1){
            v.push_back(root->val);//保存路径上的节点值
            if(root->val > i)
                root = root->left;
            else if(root->val < i)
                root = root->right;
            else
                return;
        }
    }
    int lowestCommonAncestor(TreeNode* root, int p, int q) {
        vector<int> vp,vq;
        findpath(root,vp,p);
        findpath(root,vq,q);
        int i =0;
        for(i;i<vp.size();i++){
            if(vp[i] != vq[i])
                break;//因为数组是从根节点开始插入的，所以找到第一个不重复的数值
        }
        return vp[i-1];//那么不重复数值的上一个数值就是保存的祖先节点值
    }
};