搜索二叉树最近公共祖先
题目描述（简单）
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]
讯享网
示例 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，那么p、q在根的左子树上，递归的其左子树；
同理，如果同时小于，那么都在右子树上，递归其右子树；
如果两边各一个，那就返回此时的根节点，只有他是最近公共祖先
代码
class Solution {
public: TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if(root == nullptr) return nullptr; 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; } }; 讯享网
二叉树的最近公共祖先（中等）
题目描述
基本同上，只不过这里二叉树是普通二叉树
示例 1：
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出：3
解释：节点 5 和节点 1 的最近公共祖先是节点 3 。
示例 2：
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出：5
解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。
示例 3：
提示：
树中节点数目在范围 [2, 105] 内。
-109 <= Node.val <= 109
所有 Node.val 互不相同 。
p != q
p 和 q 均存在于给定的二叉树中。
思路
这样就不能单纯用值比大小来找，需要递归的找到p、q
边界情况，根空，回空；根节点是p、q之一，回根；两个边界不多解释
之后就需要新建左右两个指针，分别dfs一起找p、q，找到了就返回，找不到就回空
这时二叉树有以下两种情况：
1、左右都不为空，因为每个节点的值唯一，所以必然是p、q在根节点两边，所以回根；
2、有一边为空，也就是在同一侧，这时不为空的以及找到p或q，而另一个还没找到，
必然是该节点孩子，所以返回该节点
整个过程是递归调用的，返回时会自底向上找到最近公共祖先。
代码
讯享网class Solution {
public: TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if(root == nullptr) return nullptr; if(root->val == p->val || root->val == q->val) return root; TreeNode* l = lowestCommonAncestor(root->left,p,q); TreeNode* r = lowestCommonAncestor(root->right,p,q); if(l&&r) return root; else return l?l:r; } };
结果
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请联系我们，一经查实，本站将立刻删除。
如需转载请保留出处：https://51itzy.com/kjqy/40147.html