Swift solution


  • 0
    class Solution {
        func lowestCommonAncestor(_ root: TreeNode?, _ p: TreeNode?, _ q: TreeNode?) -> TreeNode? {
            guard let root = root else {
                return nil
            }
            guard let p = p, let q = q else {
                return root
            }
            
            var parent = [TreeNode: TreeNode]()
            var stack = [TreeNode]()
            
            parent[root] = nil
            stack.append(root)
            while !parent.keys.contains(p) || !parent.keys.contains(q) {
                let node = stack.removeLast()
                if let leftNode = node.left {
                    parent[leftNode] = node
                    stack.append(leftNode)
                }
                if let rightNode = node.right {
                    parent[rightNode] = node
                    stack.append(rightNode)
                }
            }
            
            var ancestors: Set<TreeNode> = [p]
            var pNode: TreeNode? = parent[p]
            while pNode != nil {
                ancestors.insert(pNode!)
                pNode = parent[pNode!]
            }
            
            var qNode = q
            while !ancestors.contains(qNode) {
                if let qParent = parent[qNode] {
                    qNode = qParent
                } else {
                    break
                }
            }
            
            return q
        }
        
        func lowestCommonAncestor_Rec(_ root: TreeNode?, _ p: TreeNode?, _ q: TreeNode?) -> TreeNode? {
            if root == nil || q == nil || p == nil {
                return root
            }
            
            let left = lowestCommonAncestor_Rec(root?.left, p, q)
            let right = lowestCommonAncestor_Rec(root?.right, p, q)
            
            if left != nil && right != nil {
                return root
            }
            return left != nil ? left: right
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.