夏天做哪个网站致富,响应式布局的原理,网站开发私活,商城定制开发一、题目描述
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为#xff1a;“对于有根树 T 的两个节点 p、q#xff0c;最近公共祖先表示为一个节点 x#xff0c;满足 x 是 p、q 的祖先且 x 的深度尽可能大#xff08;一个节点也…一、题目描述
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为“对于有根树 T 的两个节点 p、q最近公共祖先表示为一个节点 x满足 x 是 p、q 的祖先且 x 的深度尽可能大一个节点也可以是它自己的祖先。” 示例 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
输入root [1,2], p 1, q 2
输出1提示
树中节点数目在范围 [2, 10^5] 内。-10^9 Node.val 10^9所有 Node.val 互不相同 。p ! qp 和 q 均存在于给定的二叉树中。
二、解题思路
如果当前节点为空或者当前节点是 p 或 q 中的一个那么返回当前节点。递归地在左子树中查找 p 和 q 的最近公共祖先。递归地在右子树中查找 p 和 q 的最近公共祖先。如果左子树和右子树中分别找到了 p 和 q那么当前节点就是最近公共祖先。如果只在左子树中找到了 p 和 q 中的一个或两个那么最近公共祖先一定在左子树中返回左子树的查找结果。如果只在右子树中找到了 p 和 q 中的一个或两个那么最近公共祖先一定在右子树中返回右子树的查找结果。
三、具体代码
class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {// 如果当前节点为空或者当前节点是 p 或 q直接返回当前节点if (root null || root p || root q) {return root;}// 递归地在左子树中查找 p 和 q 的最近公共祖先TreeNode left lowestCommonAncestor(root.left, p, q);// 递归地在右子树中查找 p 和 q 的最近公共祖先TreeNode right lowestCommonAncestor(root.right, p, q);// 如果左子树和右子树中分别找到了 p 和 q那么当前节点就是最近公共祖先if (left ! null right ! null) {return root;}// 如果只在左子树中找到了 p 和 q那么最近公共祖先一定在左子树中if (left ! null) {return left;}// 如果只在右子树中找到了 p 和 q那么最近公共祖先一定在右子树中return right;}
}四、时间复杂度和空间复杂度
1. 时间复杂度 单次访问节点对于树中的每个节点我们最多只会访问它一次。在递归函数中每个节点都会被访问一次然后它的子节点会被递归地访问。 递归深度在最坏的情况下递归的深度会达到树的高度。在二叉树中最坏情况是树退化成一条链此时递归深度为 nn 是树中节点的数量。
因此时间复杂度是 O(n)其中 n 是树中节点的数量。
2. 空间复杂度 递归调用栈由于递归的特性在递归过程中函数调用栈会保存每一层递归的信息。在最坏情况下递归的深度会达到树的高度。 递归深度与空间复杂度的关系在最坏的情况下如果树是一条链那么递归的深度就是 n此时递归调用栈将占用 O(n) 的空间。
因此空间复杂度是 O(n)其中 n 是树中节点的数量。
综上所述
时间复杂度O(n)因为每个节点最多被访问一次。空间复杂度O(n)因为递归调用栈在最坏情况下可能达到 n 的深度。
五、总结知识点 递归 递归是一种常用的算法设计方法它允许函数调用自身来解决问题。在这个代码中递归用于遍历二叉树并查找两个节点的最近公共祖先。 二叉树遍历 代码通过递归实现了二叉树的遍历具体是后序遍历先访问左右子节点再访问根节点。遍历过程中如果找到了 p 或 q 节点则递归函数会返回该节点。 逻辑判断 代码包含了多个 if 语句用于判断递归函数返回的节点是否为空从而确定最近公共祖先的位置。 树的结构 代码操作的数据结构是二叉树树中的每个节点包含值val、左子节点left和右子节点right。 最近公共祖先的定义 代码实现了一个基于最近公共祖先定义的算法即对于两个节点 p 和 q找到它们在二叉树中的最低最深的共同祖先。 边界条件处理 代码首先检查了边界条件即当前节点是否为空或等于 p 或 q这确保了递归的基本情况。 递归与回溯的结合 在递归过程中通过回溯递归返回的方式将子树中的信息传递给父节点以便在父节点做出决策。
以上就是解决这个问题的详细步骤希望能够为各位提供启发和帮助。
