[LeetCode] 236. Lowest Common Ancestor of a Binary Tree

Link : 236. Lowest Common Ancestor of a Binary Tree

문제 설명

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

Example 1:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3
Explanation: The LCA of nodes 5 and 1 is 3.

Example 2:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output: 5
Explanation: The LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.

Example 3:

Input: root = [1,2], p = 1, q = 2
Output: 1

Constraints:

• The number of nodes in the tree is in the range [2, 10<sup>5</sup>].

• -10<sup>9</sup> <= Node.val <= 10<sup>9</sup>

• All Node.val are unique.

• p != q

• p and q will exist in the tree.

문제 분석

글의 내용이 많기는 하지만 말하고자 하는 요점은 아래와 같습니다.

“2개의 노드가 만날 수 있는 가장 가까운 상위노드는 어디인가?”

위 그림과 같이 2개의 노드를 타고서 위로 올라갈때 만날 수 있는 가장 가까운 노드를 찾으면 되는 것이죠

해결 방안

그래서 저는 다음과 같이 문제를 해결하려고 했습니다.

1. p, q node에 대해서 root 에서 부터 path 배열을 각각 구한다

2. 2개의 path 정보 중에서 곂치는 노드 중 가장 낮은 위치에 있는 노드를 찾는다

path 배열을 구하기 위해서 재귀를 이용해서 문제를 풀었습니다.

해답 코드

class Solution {
    fun lowestCommonAncestor(root: TreeNode?, p: TreeNode?, q: TreeNode?): TreeNode? {
        val pathToP = ArrayList<TreeNode>()
        val pathToQ = ArrayList<TreeNode>()

        findPath(root, p, pathToP)
        findPath(root, q, pathToQ)

        var lca: TreeNode? = null

        var i = 0
        while (i < pathToP.size && i < pathToQ.size && pathToP[i] === pathToQ[i]) {
            lca = pathToP[i]
            i++
        }

        return lca
    }

    private fun findPath(root: TreeNode?, target: TreeNode?, path: ArrayList<TreeNode>): Boolean {
        if (root == null) return false

        path.add(root)

        if (root === target) return true

        if (findPath(root.left, target, path) || findPath(root.right, target, path)) {
            return true
        }

        path.removeAt(path.size - 1)
        return false
    }
}

class TreeNode(var `val`: Int = 0) {
    var left: TreeNode? = null
    var right: TreeNode? = null
}

느낀점

그래프 문제여서 처음부터 막상 겁을 먹었던 것 같습니다. 하지만 문제를 풀때에 큰 틀에서 우선 접근하고 그다음에 구현에 대해서 신경쓰니깐 그다지 어렵지 않았던 것 같습니다. 특히 AI를 사용해서도 문제를 풀어보고 있는데 정답을 바로 달라고 하는 것이 아니라 먼저 큰 틀을 생각해서 가장 이상적인 순서도를 제시하고 문제를 푸니 문제 해결 속도와 디버깅이 빨라서 생산성이 높아진것도 느낄 수 있었습니다.