剑指 Offer 68 | I. 二叉搜索树的最近公共祖先

墨蓝 2022-12-28 12:38 69阅读 0赞

**题目**

> 给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
> 
> 百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x  
> 的深度尽可能大（一个节点也可以是它自己的祖先）。”

例如，给定如下二叉搜索树: root = \[6,2,8,0,4,7,9,null,null,3,5\]  
![在这里插入图片描述][20201217085642964.png]

**示例 1:**

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
    输出: 6 
    解释: 节点 2 和节点 8 的最近公共祖先是 6。

**示例 2:**

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
    输出: 2
    解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。

**说明:**

所有节点的值都是唯一的。
    p、q 为不同节点且均存在于给定的二叉搜索树中。

--------------------

**思路：迭代法**

*  普通的二叉树可能需要自底向上遍历，但是二叉搜索树不用，因为搜索树使有序的。
 *  判断最近的公共祖先只有三种情况：
    
     *  两个结点都在左子树上，那么就让root=root->left；到左子树上进一步搜寻
     *  两个结点都在右子树上，那么就让root=root->right；到右子树上进一步搜寻
     *  结点分别在左右子数上：那么最近的公共结点肯定使root；返回root即可。

class Solution { 
    public:
        TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { 
            while(root) { 
                if (root->val > p->val && root->val > q->val) { 
                    root = root->left;
                } else if (root->val < p->val && root->val < q->val) { 
                    root = root->right;
                } else return root;
            }
            return NULL;
        }
    };

[20201217085642964.png]: /images/20221120/9208b99e5312473381d6f54d4def4881.png