Swift solution with comments (no Swift compiler option)


  • 0
    M

    Couldn't test this, Swift is not yet supported for this question, but this is a working adaption of a concise solution from another contributor to Swift.

    class Node {
        let val: Int
        var right: Node?
        var left: Node?
        
        init(_ val: Int) {
            self.val = val
        }
    }
    
    class Solution {
        func lowestCommonAncestor(_ root: Node?, _ p: Node, _ q: Node) -> Node? {
            // we break when we hit a leaf node
            // or root (the recursed node in reality) is at p or q
            if root == nil || root === p || root === q {
                return root
            }
            
            // DFS recurse left and right
            let left = lowestCommonAncestor(root?.left, p, q)
            let right = lowestCommonAncestor(root?.right, p, q)
            
            // if left is at a leaf, try to go right
            // NOTE: right might be nil, let the base condition handle it
            if left == nil {
                return right
            }
            
            // if right is at a leaf, try to go left
            // NOTE: left might be nil, let the base condition handle it
            if right == nil {
                return left
            }
            
            // both left and right are NOT nil, 
            // we have some common node that is not p or q
            return root
       }
    }
    

Log in to reply
 

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