이진 트리: 최저 공통 조상(LCA)

Leetcode 문제236. Lowest Common Ancestor of a Binary Tree를 참조할 수 있습니다.

문제 설명

이진 트리가 주어지면 트리에서 주어진 두 노드의 lowest common ancestor(LCA)를 찾으십시오.

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).”

예 1:

입력: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1출력: 3설명: 노드 5와 1의 LCA는 3입니다.

예 2:

입력: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4출력: 5설명: 노드 5와 4의 LCA는 5입니다. 노드는 LCA 정의에 따라 자신의 자손이 될 수 있기 때문입니다.

직관

우리는 p와 q를 모두 자손으로 가지는 공통의 첫 번째 부모를 찾아야 합니다.

다음 이진 트리를 고려하십시오.

입력: 루트: [1, 2, 3, 4, null, 5, 6, null, 7, null, 8, 9, 10, null, null, null, null,null, null, 11, 12]p: 8q : 11

재귀pre-order dfs traversal를 따르고 현재 노드를 p 및 q와 비교할 수 있습니다.

if(root == null ){
  return null;
}

지정된 각 노드(루트)에 대해 다음을 확인합니다.

root가 null이면 null를 반환합니다.

p와 q 중 노드 중 하나가 root 자신이라면? 일치하는 항목을 찾았다는 의미이며, 이 경우 해당 노드, 일치하는 루트를 반환해야 합니다.

따라서 이를 위해 root를 p와 q 모두와 비교할 수 있습니다.

if(root == p || root == q){
  return root;
}

왼쪽 자식에 대상 노드 p/q가 없으면 null이 됩니다. 마찬가지로 오른쪽 자식의 경우 null이 됩니다.

왼쪽 또는 오른쪽 하위 트리에서 일치하는 항목이 발견되면 재귀 호출로 다시(위로) 반환된 다음 상대 부분(왼쪽 또는 오른쪽 값)과 비교됩니다. 두 값이 모두 발견되면 왼쪽 하위 트리에서 p가 발견되고 오른쪽 하위 트리에서 q가 발견되면 현재 루트인 왼쪽 및 오른쪽의 부모가 lca로 반환됩니다.

아무것도 찾지 못하면 null이 반환됩니다.

파란색 화살표를 따라 루트 노드8의 lca(root.right, 8, 11)에서 5가 발견되면 왼쪽 자식null과 비교하여 루트8의 호출 스택에서 5가 반환됩니다. ) .

마찬가지로, 노드11는 루트3에서 재귀 호출의 결과로 반환됩니다.

마지막으로 루트 노드3의 호출 스택에서 왼쪽 노드는 8이고 오른쪽 노드는 11입니다. 이 두 값을 비교하고 둘 다 존재하므로(null이 아님) 현재 루트( 3 )가 반환되어 트리 루트1까지 반환됩니다.

복잡성 분석

Time complexity : O(N) , 여기서 N는 이진 트리의 노드 수입니다. 최악의 경우(왼쪽으로 치우침 또는 오른쪽으로 치우침) 이진 트리의 모든 노드를 방문할 수 있습니다.
Space complexity : O(N) . 왜곡된 이진 트리의 높이가 N일 수 있으므로 재귀 스택에서 사용하는 최대 공간이 N이기 때문입니다.

프로그램

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {

        if(root == null){
            return null;
        }

        if( root == p || root == q){
            return root;
        }

        TreeNode lNode = lowestCommonAncestor(root.left, p, q);
        TreeNode rNode = lowestCommonAncestor(root.right, p, q);

        if(lNode == null)
            return rNode;

        if(rNode == null)
            return lNode;

        return root;
    }
}

테스트 사례

[3,5,1,6,2,0,8,null,null,7,4]
5
1
[3,5,1,6,2,0,8,null,null,7,4]
5
4
[1,2]
1
2