LeetCode 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).”
Given the following binary tree: root = [3,5,1,6,2,0,8,null,null,7,4]

        _______3______
       /              \
    ___5__          ___1__
   /      \        /      \
   6      _2       0       8
         /  \
         7   4

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.

Note:

All of the nodes’ values will be unique.

p and q are different and both values will exist in the binary tree.

Reference Answer

사고방식 분석
주의는 BST입니다. 그러면 나누어 다스리는 전략을 사용하여 왼쪽과 오른쪽의 가장 낮은 공공 조상을 찾아냅니다.
가장 낮은 공공 조상의 정의는 두 갈래 나무에서 우리가 찾을 수 있는 가장 가까운 잎의 노드인데 이 노드는 p와 q의 조상 노드이다.만약 p나 q 자체도 자신의 조상이 될 수 있다면 주의해라.
귀속을 사용한다면 가장 중요한 것은 귀속 함수의 작용이 무엇인지 아는 것이다.이 문제에서 lowestCommonAncestor(root,p,q) 함수의 역할은 p와 q가 루트 트리에서 가장 낮은 공공 조상이 무엇인지 판단하고 반환값은 공공 조상이다.
이 문제의 패턴을 devide and conquer라고 합니다.만약 현재 노드가 그 중의 p와 q의 어떤 노드와 같다면, 노드를 찾으면 이 노드로 돌아가고, 그렇지 않으면 좌우 트리에서 각각 찾습니다.
좌우 나무 두 개가 돌아오는 것은 무엇입니까?이 귀속 함수의 정의에 따라 왼쪽 나무와 오른쪽 나무에서 p와 q의 공공 조상을 찾았고 조상이 노드 자신일 수 있음을 주의했다.그리고 좌우에서 찾은 노드에 따라 진일보한 판단을 한다.
만약 좌우측에서 찾은 결과가 비어 있지 않다면 각각 p와 q를 찾았다는 뜻이다. 그러면 LCA는 현재 노드이다.그렇지 않으면 비어있지 않은 그 결과가 원하는 것이다.
스스로 모든 가능한 경로를 직접 훑어보고 p, q가 경로의 색인 값에 근거하여 그 층수의 선후 순서를 판단하고 마지막으로 상술한 조건에 따라 출력한다고 생각했지만 결과가 계속 틀렸다. 잠시 먼저 틀어놓고 개인적으로 이 사고방식은 문제가 없다고 느꼈다.
Code

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def lowestCommonAncestor(self, root, p, q):
        """
        :type root: TreeNode
        :type p: TreeNode
        :type q: TreeNode
        :rtype: TreeNode
        """
        if not root or root == p or root == q:
            return root
        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)
        if left and right:
            return root
        return left if left else right
                

C++ 버전 추가:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root == NULL || p == root || q == root){
            return root;
        }
        TreeNode* left = lowestCommonAncestor(root->left, p, q);
        TreeNode* right = lowestCommonAncestor(root->right, p, q);
        if(left != NULL && right != NULL){
            return root;
        }
        return left ? left : right;
    }
};

Note

이 문제는 전형적인 DFS(깊이 우선 훑어보기)입니다. 이전에는 대부분 BFS(폭 우선 훑어보기)를 사용했습니다. 이런 깊이 우선 훑어보는 사상은 자신이 생각하는 출력의 모든 가능한 경로와 비슷하지만 이런 방법은 의외로 간단하고 터무니없이 그 문제 풀이 방향을 배워야 합니다

참고 문헌

[1] https://blog.csdn.net/fuxuemingzhu/article/details/51290289