力扣236——二叉树的最近公共祖先

时间:2024-02-11 23:41:34 标签:  祖先  

祝大家新年快乐呀,虽这段时间正值过年,但是我们不要忘记停下学习的脚步。今天我们一起看一到力扣上的经典二叉树OJ题,求二叉树两个结点最近的公共祖先。

https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/description/

链接给大家放在这里啦,大家一点即达

首先我们看到题目,这道题并没有告诉我们这是一棵怎么样的二叉树,不是完全二叉,也不是搜索二叉,所以这道题做起来就比较棘手,完全二叉树的话我们可以根据结点的编号查找,搜索二叉我们也可以按照大小确定范围,但是眼前这颗数完全是一个乱序的,所以这道题怎么下手呢?

方法一        

我们不妨先确定要查找的两个结点在根结点的哪边,我们拿5和8举例子

很明显。这两个结点一个在根结点的左边,一个在右边,所以他们最近公共结点肯定就是根节点。

那如果在同一边呢?比如6和4,

结点6和4都在根节点的左子树上,我们可以用刚才的方法,递归根节点的左子树,以结点5为跟,就可以求出他们最近的公共结点为5;思路有了,现在我们编写代码

我们先封装一个函数判断结点是否在这个以root为根结点的二叉树内:

bool IsTree(TreeNode*root,TreeNode* x){if(root==nullptr){return false;}return root==x||IsTree(root->left,x)||IsTree(root->right,x);}

然后我们在给定的函数内实现出这个函数。

这里教大家一个简便的方法。我们定义几个bool变量:

bool Leftp,Rightp,Leftq,Rightq;//依次代表的含义是p在左子树,P在右子树,q在左子树,q在右子树

然后我们去找p在root的那一边,把返回值给Leftp,让Rightp=!Left;

Leftp=IsTree(root->left,p);
Rightp=!Leftp;

这样写大家能理解什么意思吗?在root的左子树去找结点p的结果赋给Leftp,不管是不是在左边,右边的结果肯定就是!Leftp,假如Leftp是true,那Rightp就是false;如果Leftp是false,那Rightp就是true;二者肯定一真一假,判断q结点在哪边也是如此

Leftq=IsTree(root->left,q);
Rightq=!Leftq;

然后我们判断如果两个结点pq有一个是根节点root的话,那就返回root就可以了

if(p==root||q==root){return root;}

其次,判断,如果pq一个在根节点左边,一个在右边,那还是返回根节点。即

if((Leftp&&Rightq)||(Rightp&&Leftq))//中间用||连接是因为我们也不知道他们在哪边,反正肯定有一组是真的
{return root;
}

然后再判断他们在同一边的情况,代码运行到这里,肯定能证明他们不在同一边,我们先判断同时在左子树的情况:

    else if(Leftp&&Leftq){return lowestCommonAncestor(root->left,p,q);}

剩下的就是同时在右子树的情况:

else{return lowestCommonAncestor(root->right,p,q);}

然后我们提交,就可以看到通过啦。但是我们思考一下,这样的写法时间复杂度是很大的。如果这棵树是一个类似于单边的二叉树,也就是另外一边的结点个数很少很少,几乎全部集中在一边,且要找的两个结点都在最后,即:

我们要查找的两个结点在这个位置,它的时间复杂度是多少?可以看到,我们以3为根结点查询1和3在哪边需要走N-2次+N-3次,然后递归以10为根节点查找,再递归以8为根节点查找.......时间复杂度其实是O(N^2)的。

bool IsTree(TreeNode*root,TreeNode* x){if(root==nullptr){return false;}return root==x||IsTree(root->left,x)||IsTree(root->right,x);}TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {bool Leftp,Rightp,Leftq,Rightq;Leftp=IsTree(root->left,p);Rightp=!Leftp;Leftq=IsTree(root->left,q);Rightq=!Leftq;if(p==root||q==root){return root;}if((Leftp&&Rightq)||(Rightp&&Leftq)){return root;}else if(Leftp&&Leftq){return lowestCommonAncestor(root->left,p,q);}else{return lowestCommonAncestor(root->right,p,q);}
}

方法二

下面我们介绍第二种方法

第二种方式是我们记录两个结点的路径,即从根结点到找到他们之间所有的结点。例如:

结点6的路径是3->5->6,结点4的路径是3->5->2->4,把他们都放在两个栈里面,比较栈的特点是后进先出,然后比较这个两个栈的第一个相同的栈顶元素。这样的话我们最坏无非就是遍历2次这棵树就可以,定义两个栈,算是以空间换时间。下面我们开始实现

我们首先需要在原函数定义两个栈,一个用于存放p结点的路径,一个存放q结点的路径

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
stack<TreeNode*> ppath;
stack<TreeNode*>qpath;
}

然后我们需要封装一个函数用来求结点走过的路径Getpath();参数需要根节点,待求结点,栈,即

bool Getpath(TreeNode* root, TreeNode* x, stack<TreeNode*>& path)//传引用是为了我们在调用这个函数时对这个栈的修改可以随时生效,不需要再拷贝

用bool类型是为了我们找到这个结点时就直接返回不再往下走。

下面我们实现这个函数,首先判断根节点为空,那就返回false,接下来先把根节点入栈,然后判断根结点是要求的路径的结点,是的话返回true;

bool Getpath(TreeNode* root, TreeNode* x, stack<TreeNode*>& path)
{if (root == nullptr){return false;}path.push(root);if (root == x){return true;}
}

代码走到这里,那就证明根结点不是x,我们递归左子树,如果左子树为真,返回true;左子树遇到空结点返回false,下来递归右子树,右子树也是如此;

if (Getpath(root->left, x, path))return true;if (Getpath(root->right, x, path))return true;

代码走到这里,证明根节点及它的左右孩子结点都不是x,我们需要把这个根节点出栈的,比如:

比如我们求结点4的路径,代码运行到查找5的左孩子时,6先进栈,然后递归6的左右子树,都为空,已经把6的左右子树都查找完毕,所以4的路径不经过结点6,那这个时候需要让6出栈,然后返回false,返回上一层递归。

if (root != x){path.pop();}return false;

这个函数就封装完成。

下面写原函数,原函数我们首先要定义两个栈,上面已经定义过,这个是我们先走一遍p的路径,再走一遍q的路径,这个时候ppath和qpath两个栈里面存放着p和q的路径,我们需要让这两个栈的大小相等,因为从根节点到最近公共祖先肯定是完全一样的,这样才能找出公共路径。

while (ppath.size() != qpath.size())
{if (ppath.size() > qpath.size())ppath.pop();elseqpath.pop();
}

这个时候两栈存放的数据个数相等,只需比较栈顶元素是否相等,不相等再同时出栈,相等时返回栈顶元素就可以啦。

while (ppath.top() != qpath.top())
{ppath.pop();qpath.pop();
}
return ppath.top();

这样代码就能提交过啦。时间复杂度也很乐观。

bool Getpath(TreeNode* root, TreeNode* x, stack<TreeNode*>& path)
{if (root == nullptr){return false;}path.push(root);if (root == x){return true;}if (Getpath(root->left, x, path))return true;;if (Getpath(root->right, x, path))return true;if (root != x){path.pop();}return false;
}
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {stack<TreeNode*> ppath;
stack<TreeNode*>qpath;
Getpath(root, p, ppath);
Getpath(root, q, qpath);
while (ppath.size() != qpath.size())
{if (ppath.size() > qpath.size())ppath.pop();elseqpath.pop();
}
while (ppath.top() != qpath.top())
{ppath.pop();qpath.pop();
}
return ppath.top();}
来源:分享自作者个人站点/博客

智能推荐

祝大家新年快乐呀&#xff0c;虽这段时间正值过年&#xff0c;但是我们不要忘记停下学习的脚步。今天我们一起看一到力扣上的经典二叉树OJ题&#xff0c;求二叉树两个结点最近的公共祖先。 https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/description/ 链接给大家放在这里啦&#xff0c;大家一点即达 首先我

标签:祖先  

题目描述 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为&#xff1a;“对于有根树 T 的两个节点 p、q&#xff0c;最近公共祖先表示为一个节点 x&#xff0c;满足 x 是 p、q 的祖先且 x

标签:祖先  

一、题目 1、题目描述 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为:“对于有根树 T 的两个节点 p、q,最近

标签:祖先  

一、题目 1、题目描述 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为:“对于有根树 T 的两个节点 p、q,最近公共祖先表示为一个节点 x,满足 x 是 p、q 的祖先且 x 的深度

标签:祖先  

题目描述 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为&#xff1a;“对于有根树 T 的两个节点 p、q&#xff0c;最近公共祖先表示为一个节点 x&#xff0c;满足 x 是 p、q 的祖先且 x 的深度尽可能大&#xff08;一个节点也可以是它自己的祖先&#xff09;。” 示例 1&#xff1a;

标签:题解  

一、题目大意给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。百度百科中最近公共祖先的定义为:“对于有根树 T 的两个节点 p、q,最近公共祖先表示为一个节点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。”示例 1:输入:root = [3

标签:祖先  二叉树  Lowest  LeetCode  Common  

代码随想录二刷 &#xff5c; 二叉树 &#xff5c; 二叉搜索树的最近公共祖先 题目描述解题思路代码实现 题目描述 235.二叉搜索

标签:祖先  

最近公共祖先 概念 给定一棵有n个节点的树&#xff0c;树中的两个节点u和v的最近公共祖先lca&#xff0c;有以下定义 &#xff08;1&#xff09;lca既是u的祖先&#xff0c;又是v的祖先 &

标签:祖先  

描述&#xff1a; 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为&#xff1a;“对于有根树 T 的两个节点 p、q&#xff0c;最近公共祖先表示为一个节点 x&#xff0c;满足 x 是 p、q 的祖先且 x 的深度尽可能大&#xff08;一个节点也可以是它自己的祖先&#xff09;。”

标签:祖先  

一、题目给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。百科中最近公共祖先的定义为:对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。二、示例2.1> 示例 1:

标签:祖先  剑指  二叉树  LeetCode  Offer  

「观前提醒」「文章仅供学习和参考,如有问题请在评论区提出」目录前言定义性质求 LCA倍增算法Trajan 算法树链剖分基本概念基本性质具体实现参考资料前言简单的模板整理,只是概括了一下具体的实现方法(说到底是给自己写的),如果看不明白可以去看原视频(讲的很好),链接在参考资料里。

标签:祖先  LCA  

530. 二叉搜索树的最小绝对差 1. LeetCode链接 力扣&#xff08;LeetCode&#xff09;官网 - 全球极客挚爱的技术成长平台 2. 题目描述 3. 解法         中序遍历&#xff0c;记录前一个指针&#xff0c;并记录前一个指针和当前指针的绝对差值。递归。

标签:祖先  

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

标签:祖先  剑指  LeetCode  Offer  

题目1&#xff1a;530 二叉搜索树的最小绝对差 题目链接&#xff1a;530 二叉搜索树的最小绝对差 题意 返回二叉搜索树的两个不同节点间的最小差值&#xff08;是一个正数&#xff0c;取绝对值&#xff09; 注意利用二叉搜索树的性质  中序遍历得到的是一个有序单调递增的数组 递归

标签:祖先  

目录 Leetcode 530.二叉搜索树的最小绝对差 Leetcode 501.二叉搜索树中的众数

标签:祖先  

二叉树的最近公共祖先力扣题目链接(opens new window)给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。百度百科中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。”例如,给定如下二叉树: root = [3,5,1,6,2,0,8,null,null,7,4]

标签:递归  遍历  祖先  机制  二叉树  

题目1&#xff1a;235 二叉搜索树的最近公共祖先 题目链接&#xff1a;235 二叉搜索树的最近公共祖先 题意 找出二叉搜索树中两个指定节点的最近公共祖先 二叉搜索树中节点各不相同&#xff0c;且两个指定的节点均存在与二叉搜索树中&#xff0c;也不同 递归 递归三部曲&#xff1a; 1&#xff09;递归函数的参数和返回值

标签:节点  

530.二叉搜索树的最小绝对差 1、题目链接&#xff1a;力扣&#xff08;LeetCode&#xff09;官网 - 全球极客挚爱的技术成长平台 2、文章讲解&#xff1a;力扣&#xff08;LeetCode&#xff09;官网 - 全球极客挚爱的技术成长平台 3、题目&#xff1a; 给你一棵所有节点为非负值的二叉搜索树&#xff0c;请你计算树中任意两节点的差的绝对值的最小值。 示例&#xff1a;

标签:祖先  

一、题目大意给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。百度百科中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。”例如,给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]

标签:祖先  简单  Lowest  Common  LeetCode  

二叉树part08 235.二叉搜索树的最近公共祖先 701.二叉搜索树中的插入操作 450.删除二叉搜索树中的节点 235. 二叉搜索树的最近公共祖先 方法一&#xff

标签:节点  

二叉树part08 235.二叉搜索树的最近公共祖先 701.二叉搜索树中的插入操作 450.删除二叉搜索树中的节点 235. 二叉搜索树的最近公共祖先 方法一&#xff1a;递归法&#xff08;利用二叉搜索树性质&#xff09;

标签:节点  

&#x1f525;博客主页&#xff1a; 【小扳_-CSDN博客】 ❤感谢大家点赞&#x1f44d;收藏⭐评论✍  

标签:解法  

猜你喜欢

654.最大二叉树 给定一个不含重复元素的整数数组。一个以此数组构建的最大二叉树定义如下&#xff1a; 二叉树的根是数组中的最大元素。 左子树是通过数组中最大值左边部分构造出的最大二叉树。

标签:二叉树  

目录 二叉搜索树的最近公共祖先二叉搜索树中的插入操作删除二叉搜索树中的节点普通二叉树的删除方式 LeetCode 235. 二叉搜索树的最近公共祖先

标签:节点  

最近公共祖先 最近公共祖先简称 LCA&#xff08;Lowest Common Ancestor&#xff09;。两个节点的最近公共祖先&#xff0c;就是这两个点的公共祖先里面&#xff0c;离根最远的那个。 题目链接 祖

标签:祖先  

1123 Lowest Common Ancestor of Deepest Leaves 最深叶节点的最近公共祖先Description:Given the root of a binary tree, return the lowest common ancestor of its deepest leaves.Recall that:The node of a binary tree is a leaf if and only if it has no childrenThe depth of the root of the tree is 0. if the depth o

标签:节点  最深  祖先  Lowest  LeetCode  

文章目录 题目 104. 二叉树的最大深度题解后序遍历 递归实现后序遍历 迭代实现层序遍历

标签:深度  

目录 题目地址&#xff1a; 题目&#xff1a;

标签:直径  

目录 题目地址&#xff1a; 题目&#xff1a;

标签:直径  

617.合并二叉树&#xff08;经典&#xff09; 合并二叉树是操作两棵树的题目里面很经典的&#xff0c;如何对两棵树遍历以及处理&#xff1f; 给定两个二叉树&#xff0c;想象当你将它们中的一个覆盖到另一个上时&#xff0c;两个二叉树的

标签:二叉树  

目录 前序遍历与后续遍历 题目地址&#xff1a;

标签:二叉树  

目录 题目地址&#xff1a; 题目&#xff1a;

标签:二叉树  

700 二叉搜索树中的搜索 给定二叉搜索树&#xff08;BST&#xff09;的根节点和一个值。 你需要在BST中找到节点值等于给定值的节点。 返回以该节点为根的子树。 如果节点不存在&#xff0c;则返回 NULL。 例如&#xff0c;

标签:二叉树  

Problem: 124. 二叉树中的最大路径和

标签:递归  

文章目录 题目 101. 对称二叉树题解方式一 递归方式二 迭代

标签:对称  

动态规划 思路&#xff1a; 假设 dp[i][j] 是 text1[0:i] 和 text2[0:j] 最长公共子序列的长度&#xff1b;则 dp[0][j] &#61; 0&#xff0c;&#xff08;空字符串和任何字符串的最长公共子序列的长度都是 0&#xff09;&#xff1b;同理 dp[i][j] &#61; 0&#xff1b;状态转移方程&#xff1a; 当 text1[i - 1] &#61; text2[j - 1] 时&#xff0c;dp[i][j] &#61; dp[i - 1][j - 1] &#43; 1&#xff1b;否

标签:序列  

剑指 Offer&#xff08;第2版&#xff09;面试题 68&#xff1a;树中两个结点的最低公共祖先 剑指 Offer&#xff08;第2版&#xff09;面试题 68&#xff1a;树中两个结点的最低公共祖先

标签:结点  

力扣107 二叉树的层序遍历题目:给你二叉树的根节点 root ,返回其节点值 自底向上的层序遍历 。 (即按从叶子节点所在层到根节点所在的层,逐层从左向右遍历)示例 1:输入:root = [3,9,20,n

标签:遍历  二叉树  力扣  

Problem: 102. 二叉树的层序遍历

标签:遍历  

&#x1f468;‍&#x1f3eb; 题目地址

标签:递归  

Problem: 101. 对称二叉树

标签:递归  

&#x1f468;‍&#x1f3eb; 题目地址

标签:递归  

力扣日记&#xff1a;【二叉树篇】538. 把二叉搜索树转换为累加树 日期&#xff1a;2023.1.19 参考&#xff1a;代码随想录、力扣 ps&#xff1a;因为准备组会汇报又搁置了好久&#xff08

标签:转换为  

力扣105 根据先序遍历以及中序遍历构建二叉树题目:给定两个整数数组 preorder 和 inorder ,其中 preorder 是二叉树的先序遍历, inorder 是同一棵树的中序遍历,请构造二叉树并返回其根节点。示例 1:

标签:遍历  二叉树  力扣  

&#x1f468;‍&#x1f3eb; 题目地址 &#

标签:递归  

文章目录 说明题目 450. 删除二叉搜索树中的节点题解递归实现 题目 701. 二叉

标签:力扣  

相关问题

相关文章

热门文章

推荐文章

相关标签