自助建站系统模板,大连装修网站推广,福建网站建建设,撰写网站策划书题目
235. 二叉搜索树的最近公共祖先
中等 #xff08;简单#xff09;
相关标签
树 深度优先搜索 二叉搜索树 二叉树
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为#xff1a;“对于有根树 T 的两个结点 p、q简单
相关标签
树 深度优先搜索 二叉搜索树 二叉树
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为“对于有根树 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 为不同节点且均存在于给定的二叉搜索树中。
思路和解题方法 使用迭代的方式进行查找。首先将 ancestor 初始化为根节点 root。然后在一个无限循环中进行以下判断 如果 p-val 和 q-val 都小于 ancestor-val说明 p 和 q 都在 ancestor 的左子树中因此将 ancestor 更新为 ancestor-left。如果 p-val 和 q-val 都大于 ancestor-val说明 p 和 q 都在 ancestor 的右子树中因此将 ancestor 更新为 ancestor-right。如果以上两个条件都不满足说明 p 和 q 分别位于 ancestor 的左右子树中或者其中一个节点就是 ancestor。此时找到了最近公共祖先退出循环。 最后返回 ancestor 即为最近公共祖先的节点。 由于输入的二叉搜索树符合规范且假设 p 和 q 一定存在于树中因此该算法可以正确找到最近公共祖先。 复杂度 时间复杂度: O(n) 时间复杂度O(n)其中 nnn 是给定的二叉搜索树中的节点个数。分析思路与方法一相同。 空间复杂度 O(1) 空间复杂度O(1)。 c 代码
class Solution {
public:// 返回二叉搜索树中p和q节点的最近公共祖先TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {TreeNode* ancestor root; // 初始化最近公共祖先为根节点rootwhile (true) {if (p-val ancestor-val q-val ancestor-val) { // 如果p、q都小于ancestor说明p、q在ancestor的左子树中ancestor ancestor-left; // 将ancestor更新为其左子树的节点}else if (p-val ancestor-val q-val ancestor-val) { // 如果p、q都大于ancestor说明p、q在ancestor的右子树中ancestor ancestor-right; // 将ancestor更新为其右子树的节点}else { // 如果p、q分别位于ancestor的左右子树中或者其中一个节点就是ancestor则找到了最近公共祖先退出循环break;}}return ancestor; // 返回最近公共祖先}
};附递归版本迭代版本容易懂
class Solution {
public:// 返回二叉搜索树中p和q节点的最近公共祖先TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {if (root-val p-val root-val q-val) { // 如果root的值大于p和q的值则说明p和q都在root的左子树中继续往root的左子树中搜索return lowestCommonAncestor(root-left, p, q);} else if (root-val p-val root-val q-val) { // 如果root的值小于p和q的值则说明p和q都在root的右子树中继续往root的右子树中搜索return lowestCommonAncestor(root-right, p, q);} else {return root; // 否则root为最近公共祖先直接返回root}}
};觉得有用的话可以点点赞支持一下。
如果愿意的话关注一下。会对你有更多的帮助。 每天都会不定时更新哦 人 。
