LeetCode习题:二叉树的最近公共祖先
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了LeetCode习题:二叉树的最近公共祖先,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2366字,纯文字阅读大概需要4分钟。
内容图文
![LeetCode习题:二叉树的最近公共祖先](/upload/InfoBanner/zyjiaocheng/986/a312973457604b75b10963171f1299ee.jpg)
题目描述:给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。百度百科中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。”
####例如,给定如下二叉树: root = [3,5,1,6,2,0,8,null,null,7,4]
示例:
例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。因为根据定义最近公共祖先节点可以为节点本身。
题解:存储父节点(Leetcode官方题解)
解题思路:我们可以用哈希表存储所有节点的父节点,然后我们就可以利用节点的父节点信息从 p 结点开始不断往上跳,并记录已经访问过的节点,再从 q 节点开始不断往上跳,如果碰到已经访问过的节点,那么这个节点就是我们要找的最近公共祖先。
- 1.从根节点开始遍历整棵二叉树,用哈希表记录每个节点的父节点指针。
- 2.从 p 节点开始不断往它的祖先移动,并用数据结构记录已经访问过的祖先节点。
- 3.同样,我们再从 q 节点开始不断往它的祖先移动,如果有祖先已经被访问过,即意味着这是 p 和 q 的深度最深的公共祖先,即 LCA 节点。
解题语言: Swift
class TreeNode {
var val: Int = 0
var left: TreeNode?
var right: TreeNode?
init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
self.val = val
self.left = left
self.right = right
}
};
class NearestPublicParentNode {
// 所有父节点
var parent: [Int: TreeNode] = [Int: TreeNode]()
// 访问过的节点
var visited: [Int] = [Int]()
// 存储所有父节点
func dfs(root: TreeNode) {
if root.left != nil {
parent[root.left!.val] = root
dfs(root: root.left!)
}
if root.right != nil {
parent[root.right!.val] = root
dfs(root: root.right!)
}
}
func lowestCommonAncestor(_ root: TreeNode?, _ p: TreeNode?, _ q: TreeNode?) -> TreeNode? {
var newP = p, newQ = q
if root == nil {
return nil
}
dfs(root: root!)
while newP != nil {
visited.append(newP!.val)
newP = parent[newP!.val]
}
while newQ != nil {
if visited.contains(newQ!.val) {
return newQ
}
newQ = parent[newQ!.val]
}
return nil
}
}
复杂度分析:
时间复杂度:O(N),其中 N 是二叉树的节点数。二叉树的所有节点有且只会被访问一次,从 p 和 q 节点往上跳经过的祖先节点个数不会超过 N,因此总的时间复杂度为 O(N)。
空间复杂度:O(N) ,其中 N 是二叉树的节点数。递归调用的栈深度取决于二叉树的高度,二叉树最坏情况下为一条链,此时高度为 N,因此空间复杂度为 O(N),哈希表存储每个节点的父节点也需要 O(N) 的空间复杂度,因此最后总的空间复杂度为 O(N)。
题目来源:LeetCode
内容总结
以上是互联网集市为您收集整理的LeetCode习题:二叉树的最近公共祖先全部内容,希望文章能够帮你解决LeetCode习题:二叉树的最近公共祖先所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。