LeetCode - 236. Lowest Common Ancestor of a Binary Tree (Swift)

 

https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/

LeetCode - The World's Leading Online Programming Learning Platform

 

간단한 트리 문제, 가장 낮은 공통 조상 노드를 찾는 문제

 

 

조상 노드가 될 수 있는 경우의 수는 4가지

1. 노드에 어떤 값도 들어오지 않았을 때 → 전달해줄 값이 없음
2. 노드가 주어진 p 또는 q 일 때→ 자기자신을 전달
3. 오른쪽, 왼쪽 양쪽에서 값을 전달 받았을 때 → 자기자신 전달 == 공통노드!!!
4. 왼쪽 or 오른쪽 중에 한쪽에서만 값을 전달 받았을 때 → 들어온 쪽을 그대로 흘려보내기

 

즉, 왼쪽 오른쪽 양쪽에서 값을 리턴 받는 노드가 공통노드임!!

왼쪽에서 오는 값과 오른쪽에서 오는 값을 알 수 있는 함수를 만들자

즉, 어떤 값을 리턴할 수 있는지 아는 함수를 만들고 재귀적으로 사용하면 됨

(빠져나오는 case는 루트노드가 끝났을때)

 

 

 

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? {
        if root == nil {
            return nil
        }
        
        var left = lowestCommonAncestor(root?.left, p, q)
        var right = lowestCommonAncestor(root?.right, p, q)
        
        if root === p || root === q {
            return root
        } else if left != nil, right != nil {
            return root
        }
        return (left != nil ? left : right)
    }
}

 

left, right를 통해서 각 노드들의 자식노드로 계속 함수를 재귀 호출하고 있음

 

만약에 노드에 아무런 값이 없다면

-> return nil

 

if 문 첫번째 (class의 인스턴스 비교를 위해서 === 연산자 사용)

만약 루트가 p 또는 q 라면 자기 자신을 리턴하면 됨

-> return root

 

else if 문

만약 양쪽에서 값이 모두 들어왔을 때.

즉 오른쪽, 왼쪽에서 모두 값을 전달 받았을 때 == 공통노드!

-> return root

 

두 가지의 경우가 아닐 경우

즉, 왼쪽이 nil이 아니라면 return left , 오른쪽이 nil이 아니라면 return right

 

 

라고 생각하고 풀면 되는 문제

더 좋은 풀이 있다면 공유 부탁드립니다!