动态公司网站设计,建设部注册网站,seo在线培训机构,初爱ねんね免费720p作者简介#xff1a;大家好#xff0c;我是未央#xff1b; 博客首页#xff1a;未央.303 系列专栏#xff1a;牛客面试必刷TOP101 每日一句#xff1a;人的一生#xff0c;可以有所作为的时机只有一次#xff0c;那就是现在#xff01;#xff01;#xff01;… 作者简介大家好我是未央 博客首页未央.303 系列专栏牛客面试必刷TOP101 每日一句人的一生可以有所作为的时机只有一次那就是现在 文章目录
前言
一、二叉搜索树的最近公共祖先
题目描述
解题分析
二、用两个栈实现队列
题目描述
解题分析
总结 前言
一、二叉搜索树的最近公共祖先
题目描述 描述 给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。 1.对于该题的最近的公共祖先定义:对于有根树T的两个节点p、q最近公共祖先LCA(T,p,q)表示一个节点x满足x是p和q的祖先且x的深度尽可能大。在这里一个节点也可以是它自己的祖先. 2.二叉搜索树是若它的左子树不空则左子树上所有节点的值均小于它的根节点的值 若它的右子树不空则右子树上所有节点的值均大于它的根节点的值 3.所有节点的值都是唯一的。 4.p、q 为不同节点且均存在于给定的二叉搜索树中。 数据范围: 3节点总数10000 0节点值10000 举例说明 如果给定以下搜索二叉树: {7,1,12,0,4,11,14,#,#,3,5}如下图: 示例1 示例2 解题分析 解题思路二叉搜索树的定义 二叉搜索树是一种特殊的二叉树它的每个节点值大于它的左子节点且大于全部左子树的节点值小于它右子节点且小于全部右子树的节点值。因此二叉搜索树一定程度上算是一种排序结构。 图示举例说明 思路 二叉搜索树没有相同值的节点因此分别从根节点往下利用二叉搜索树较大的数在右子树较小的数在左子树可以轻松找到p、q //节点值都不同可以直接用值比较
while(node.val ! target) { path.add(node.val);//小的在左子树if(target node.val) node node.left;//大的在右子树else node node.right;
}直接得到从根节点到两个目标节点的路径这样我们利用路径比较就可以找到最近公共祖先。 解题步骤 step 1根据二叉搜索树的性质从根节点开始查找目标节点当前节点比目标小则进入右子树当前节点比目标大则进入左子树直到找到目标节点。这个过程用数组记录遇到的元素。step 2分别在搜索二叉树中找到p和q两个点并记录各自的路径为数组。step 3同时遍历两个数组比较元素值最后一个相等的元素就是最近的公共祖先。 图示过程解析 代码编写 二、用两个栈实现队列
题目描述 描述 用两个栈来实现一个队列使用n个元素来完成 n 次在队列尾部插入整数(push)和n次在队列头部删除整数(pop)的功能。 队列中的元素为int类型。保证操作合法即保证pop操作时队列内已有元素。 数据范围n≤1000 要求存储n个元素的空间复杂度为 O(n) 插入与删除的时间复杂度都是 O(1)。 示例1 示例2 解题分析 解题思路 双栈法推荐使用 思路 元素进栈以后只能优先弹出末尾元素但是队列每次弹出的却是最先进去的元素如果能够将栈中元素全部取出来才能访问到最前面的元素此时可以用另一个栈来辅助取出。 解题步骤 step 1push操作就正常push到第一个栈末尾。step 2pop操作时优先将第一个栈的元素弹出并依次进入第二个栈中。 //将第一个栈中内容弹出放入第二个栈中
while(!stack1.isEmpty()) stack2.push(stack1.pop()); step 3第一个栈中最后取出的元素也就是最后进入第二个栈的元素就是队列首部元素要弹出此时在第二个栈中可以直接弹出。step 4再将第二个中保存的内容依次弹出依次进入第一个栈中这样第一个栈中虽然取出了最里面的元素但是顺序并没有变。 //再将第二个栈的元素放回第一个栈
while(!stack2.isEmpty()) stack1.push(stack2.pop());图示过程解析 代码编写 总结
