精选力扣500题第17题 LeetCode 33. 搜索旋转排序数组【c++详细题解】

深藏阁楼爱情的钟 2021-07-24 11:18 386阅读 0赞

### 目录 ###

*   *   *  1、题目
         *  2、思路
         *  3、代码

### 1、题目 ###

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

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

**示例 1：**

![f5afd7de3d95e88c914da24d7a2422ae.png][]

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

**示例 2：**

![6be57981a2e1f827f5bc554e09084d37.png][]

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

**示例 3：**

输入：root = [1,2], p = 1, q = 2
    输出：1

**提示：**

*  树中节点数目在范围 `[2, 105]`内。
 *  `-109 <= Node.val <= 109`
 *  所有 `Node.val` 互不相同 。
 *  `p != q`
 *  `p`和`q`均存在于给定的二叉树中。

### 2、思路 ###

**(递归)**

递归此函数，意义是在`root`这棵树找到`p`和`q`的最近公共祖先

*  1、若当前节点`root == p`，则表示`q`点一定在`root`的左右子树其中一处，则最近的公共结点肯定是`root`
 *  2、若当前节点`root == q`，则表示`p`点一定在`root`的左右子树其中一处，则最近的公共结点肯定是`root`
 *  3、若`1`和`2`情况都不是，则`p`和`q`的最近公共祖先要么在`root`的左子树，要么在`root`的右子树，则直接递归到`root->left`和`root->right`进行搜索，若递归完后，左子树返回`null`表示没找到，那答案肯定是在右子树，同理，右子树返回`null`表示没找到，那答案肯定是在左子树
 *  4、若3情况中左右子树都找不到`p`和`q`的最近公共祖先，则表示`p`点和`q`点分别在不同的左右子树，则`root`就是他们的最近公共祖先

### 3、代码 ###

/** * 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) { 
            if(root == NULL || root == p || root == q) return root;
            TreeNode *left = lowestCommonAncestor(root->left, p, q);
            TreeNode *right = lowestCommonAncestor(root->right, p, q);
            if(left == NULL) return right;
            if(right == NULL) return left;
            return root;
        }
    };

**原题链接：** [236. 二叉树的最近公共祖先][236.]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70]

[f5afd7de3d95e88c914da24d7a2422ae.png]: /images/20210724/f78fab598fd64152bca8d6442733f479.png
[6be57981a2e1f827f5bc554e09084d37.png]: /images/20210724/0cc91d7e78e347ada39cb489cf4da141.png
[236.]: https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70]: /images/20210724/90cb99862484451d8d25231edc8b00e0.png