swift算法(二叉搜索树的最近公共祖先)
1、描述
给定一个二叉树,找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为:“对于有根树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
例1:输入:root = [6, 2, 8, 0, 4, 7, 9, null, null, 3, 5], p = 2,q = 4
输出:2
解释:节点 2 和节点 4 的最近公共祖先是2,因为根据定义最近公共节点可以为节点本身
2、算法
二叉搜索树BST的性质:
节点N 左子树上的所有节点的值都小于等于节点N 的值
节点N 右子树上的所有节点的值都大于等于节点N 的值
左子树和右子树也都是 BST
1)递归
思想:节点p,q 的最近公共祖先(LCA)是距离这两个节点最近的公共祖先节点。在这里 最近 考虑的是节点的深度。
算法:
从根节点开始遍历树
如果节点p 和节点q 都在右子树上,那么以右孩子为根节点继续 1 的操作
如果节点p 和节点q 都在左子树上,那么以左孩子为根节点继续 1 的操作
如果条件 2 和条件 3 都不成立,这就意味着我们已经找到节p 和节点q 的 LCA 了
时间复杂度:O(n)
func lowestCommonAncestor(_ root : TreeNode?, _ p : TreeNode?, _ q : TreeNode?)->TreeNode?{
/*递归 O(n)*/
let parentVal : Int = (root?.val)!
let pVal : Int = (p?.val)!
let qVal : Int = (q?.val)!if pVal > parentVal && qVal > parentVal {
return lowestCommonAncestor(root?.right, p, q)
}else if pVal < parentVal && qVal < parentVal{
return lowestCommonAncestor(root?.left, p, q)
}else{
return root
}
}
2)迭代
思想:与递归类似,不同之处在于是用迭代的方法替代了递归来遍历整棵树
时间复杂度:O(n)
func lowestCommonAncestor(_ root : TreeNode?, _ p : TreeNode?, _ q : TreeNode?)->TreeNode?{
/*
迭代
*/
let pVal : Int = (p?.val)!
let qVal : Int = (q?.val)!var node = rootwhile node != nil {
let parentVal : Int = (node?.val)!
//如果节点p 和节点q 都在右子树上,那么以右孩子为根节点继续操作
if pVal > parentVal && qVal > parentVal {
return lowestCommonAncestor(root?.right, p, q)
}else if pVal < parentVal && qVal < parentVal{
//如果节点p 和节点q 都在左子树上,那么以左孩子为根节点继续操作
return lowestCommonAncestor(root?.left, p, q)
}else{
return node
}
}
return nil
}
【swift算法(二叉搜索树的最近公共祖先)】
推荐阅读
- 画解算法(1.|画解算法:1. 两数之和)
- Guava|Guava RateLimiter与限流算法
- java中如何实现重建二叉树
- 一个选择排序算法
- SG平滑轨迹算法的原理和实现
- Swift中willSet和didSet的简述
- 《算法》-图[有向图]
- Hacking|Hacking with iOS: SwiftUI Edition - SnowSeeker 项目(一)
- 二叉树路径节点关键值和等于目标值(LeetCode--112&LeetCode--113)
- LeetCode算法题-11.|LeetCode算法题-11. 盛最多水的容器(Swift)