记一下刚才刷题给我的感受

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 1699 天前的主题，其中的信息可能已经有所发展或是发生改变。

本人菜鸟，之前刷题中断了，现在又开始从数据结构开始刷，最开始是二叉树。

今天的题是寻找最小公共父节点。由于我是在 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 行就搞定了，这就是差距啊。。。以后自己写完还是应该多看看别人的思路与解法。

还有一点就是，最开始我的写完以后会有超时，看了例子应该是只有左子树或者右子树的情况，后来就又补上了判断。

最后还有一点想请教大佬，我分别提交自己和别人的解法后，时间差不多，但是内存会有差别。

请问这点差别是一定范围内随机的，还是说我的就是快一点？？？（也不可能吧）

最后附图：

WX20200331-223042@2x.png