BinaryTree_Leetcode_236. Lowest Common Ancestor of a Binary Tree

https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/description/?envType=study-plan-v2&envId=top-100-liked

 

문제접근

• DFS를 사용하여 p, q를 탐색
• 탐색하며 지나온 TreeNode를 배열로 기록
• p,q를 찾았다면, 각자 지나온 기록 Treenode 배열에서 겹치는 마지막 element탐색
• 탐색 결과 반환

정답코드

성능이 처참하다..

831msBeats5.74%

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public var val: Int
 *     public var left: TreeNode?
 *     public var right: TreeNode?
 *     public init(_ val: Int) {
 *         self.val = val
 *         self.left = nil
 *         self.right = nil
 *     }
 * }
 */

class Solution {
    func lowestCommonAncestor(_ root: TreeNode?, _ p: TreeNode?, _ q: TreeNode?) -> TreeNode? {
        guard 
            let root = root,
            let p = p,
            let q = q
        else { return nil }
        
        var qMap = [TreeNode]()
        var pMap = [TreeNode]()

        func dfs(_ root: TreeNode?, _ p: TreeNode, _ q: TreeNode, _ history: [TreeNode]) {
            guard let root else { return }
            var newHistory = history
            newHistory.append(root)

            if root.val == p.val {
                pMap = newHistory
            }
            if root.val == q.val {
                qMap = newHistory
            }

            dfs(root.left, p, q, newHistory)
            dfs(root.right, p, q, newHistory)

        }

        dfs(root, p, q, [])

        let common = qMap.lastIndex(where: { q in
            let result:Bool = pMap.contains(where: { q.val == $0.val}) 
            return result
            })

        if let common {
            return qMap[common]
        } else{
            return nil
        }

    }
}

모범코드

1. 32ms가 걸리는, 대중적인 코드

class Solution {
    func lowestCommonAncestor(_ root: TreeNode?, _ p: TreeNode?, _ q: TreeNode?) -> TreeNode? {
       guard let root = root else { return nil }
        
        if root === p || root === q {
            return root
        }
        
        let left = lowestCommonAncestor(root.left, p, q)
        let right = lowestCommonAncestor(root.right, p, q)
        
        if left != nil && right != nil {
            return root
        }
        
        return left != nil ? left : right 
    }
}

2. 상위 0.2%의 13ms 코드

class Solution {
    func lowestCommonAncestor(_ root: TreeNode?, _ p: TreeNode?, _ q: TreeNode?) -> TreeNode? {
        guard let root = root else { return nil }

        var stack: [(TreeNode, NodeState)] = [(root, .bothPending)]
        var oneNodeFound = false
        var lcaIndex = -1

        while !stack.isEmpty {
            var (node, state) = stack.removeLast()

            if state == .bothPending {
                // Before traversing children, check if this is one of the target nodes
                if node === p || node === q {
                    if oneNodeFound {
                        return stack[lcaIndex].0  // LCA is at lcaIndex in stack
                    }
                    oneNodeFound = true
                    lcaIndex = stack.count // Store LCA candidate index
                }

                // Push back with updated state and process left child
                stack.append((node, .leftDone))
                if let left = node.left {
                    stack.append((left, .bothPending))
                }
            }
            else if state == .leftDone {
                // Process right child
                stack.append((node, .bothDone))
                if let right = node.right {
                    stack.append((right, .bothPending))
                }
            }
            else {
                // Node fully processed, check if we need to update LCA index
                if oneNodeFound && lcaIndex == stack.count {
                    lcaIndex -= 1  // Reduce LCA candidate index
                }
            }
        }

        return nil  // Should never reach here
    }
}

enum NodeState {
    case bothPending
    case leftDone
    case bothDone
}

/*

    Iterative DFS + parent tracking

    Time: O(n)
    Space: O(n)

    --------------------------------------------------------------------

    Step 1: Map every node to it's parent
    Step 2: Iterate over every node from p, to the root, and add each node to a set
    Step 3: Iterate over every node from q, to the root, and check the set

    The first node found that is common between both sets is the LCA

*/

 

재학습 코드

모범코드 1을 이해하고 내가 작성한 코드 -> 24ms

 

코드흐름:

1. let left, let right에서 dfs가 진행
2. 최하단 노드까지 진행, 최하단 노드의 left, right는 존재하지 않으므로, left, right가 nil
3. 둘 다 nil이므로, if 구문의 조건을 만족하는 경우가 없어서 nil 반환
4. 이를 반복하다 p or q와 동일한 instance가 탐색됨, 해당 instance( root ) 반환
5. left or right에 반환된 값이 하나만 존재하면 상위 노드로 해당 값 반환
6. 반복되다가, left, right가 둘 다 존재하는 경우 발생, left, right 둘 다 존재하면 해당 노드가 LCA, 그러므로 root를 반환
7. 6 경우가 발생했다면, 6경우의 상위 노드의 left or right에 LCA가 반환 될 것, 그 때, 다른 한 쪽에서는 nil이 반환됨
8. 그러면 left or right가 반복 반환되며 정답을 반환

class Solution {
    func lowestCommonAncestor(_ root: TreeNode?, _ p: TreeNode?, _ q: TreeNode?) -> TreeNode? {
        guard let root else { return nil }

        if root === q || root === p {
            return root
        }

        let left = lowestCommonAncestor(root.left, p, q)
        let right = lowestCommonAncestor(root.right, p, q)

        if left != nil && right != nil {
            return root
        }

        if let left {
            return left
        }

        if let right {
            return right
        }
        
        return nil

    }
}