本人菜鸟,之前刷题中断了,现在又开始从数据结构开始刷,最开始是二叉树。
今天的题是 寻找最小公共父节点。由于我是在 explore 里学习的二叉树,刚好之前也写过层序遍历,所以就
写出来如下实现:
func lowestCommonAncestor(_ root: TreeNode?, _ p: TreeNode?, _ q: TreeNode?) -> TreeNode? {
guard let root = root, let p = p, let q = q else { return nil }
//最开始缺少起始点----------------------------
if isThereAWayFrom(p: p, to: q) {
return p
}
if isThereAWayFrom(p: q, to: p) {
return q
}
//最开始缺少终点----------------------------
var tmp = [TreeNode]()
tmp.append(root)
var lca = root
while tmp.count > 0 {
let popNode = tmp.removeFirst()
if isThereAWayFrom(p: popNode, to: p) && isThereAWayFrom(p: popNode, to: q) {
lca = popNode
}
if let left = popNode.left {
tmp.append(left)
}
if let right = popNode.right {
tmp.append(right)
}
}
return lca
}
func isThereAWayFrom(p: TreeNode?, to q: TreeNode?) -> Bool {
if p?.val == q?.val {
return true
}
if p?.left == nil && p?.right == nil {
return false
}
return isThereAWayFrom(p: p?.left, to: q) || isThereAWayFrom(p: p?.right, to: q)
}
前几天刷题做出来以后就过去了,今天我看了一下最高赞的 Java 写法,只有 4 行,换成 swift 如下:
func lowestCommonAncestor(_ root: TreeNode?, _ p: TreeNode?, _ q: TreeNode?) -> TreeNode? {
if root == nil || root?.val == p?.val || root?.val == q?.val { return root }
let left = lowestCommonAncestor(root?.left, p, q)
let right = lowestCommonAncestor(root?.right, p, q)
return left == nil ? right : right == nil ? left : root
}
虽然评论里说了最后一行不太容易理解应该展开写,但是这种思路我还是没想到的,感觉就是当头一棒。我写了那么多,别人 4 行就搞定了,这就是差距啊。。。以后自己写完还是应该多看看别人的思路与解法。
还有一点就是,最开始我的写完以后会有超时,看了例子应该是只有左子树或者右子树的情况,后来就又补上了判断。
最后还有一点想请教大佬,我分别提交自己和别人的解法后,时间差不多,但是内存会有差别。
请问这点差别是一定范围内随机的,还是说我的就是快一点???(也不可能吧)
最后附图:
1
fishCatcher 2020-03-31 22:45:36 +08:00 via iPhone
leetcode 运行时间波动很大,要自己分析复杂度
|
2
susecjh 2020-03-31 22:47:06 +08:00
多看看别人的思想,Runtime 不一定是正确的
|
3
magic3584 OP |
4
ayase252 2020-03-31 22:52:51 +08:00 via iPhone
实际运行时间是有波动的,理论分析复杂度才是正解
|
5
guolaopi 2020-03-31 22:54:08 +08:00
#1 说得对。。同一套代码,刷新提交几次你会发现自己能打败自己。。。。
|
6
hbolive 2020-04-01 09:35:21 +08:00
具体代码不做评论,但是短不一定好啊。。
|
7
sunzongzheng 2020-04-01 10:11:20 +08:00
|