leetcode - lowest common ancestor of a binary tree(java)

level - medium

[문제 내용]
주어진 이진 트리에서 p와 q의 공통된 조상을 찾아 반환(자기자신도 조상에 포함)

[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

[해결 방법]
재귀를 활용하여 왼쪽 오른쪽 탐색하며
해당하는 후손을 찾았을 경우 후손을 저장하고 true 를 반환해
해당 true를 반환받은 곳도 모두 저장한다.
그렇게 찾은 직계들을 비교하여 공통된 직계를 찾아 반환한다.

TreeNode 구조는 아래와 같다.

public class TreeNode {
     int val;
     TreeNode left;
     TreeNode right;
     TreeNode(int x) { val = x; }
 }

해결 코드는 아래와 같다.

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        ArrayList<TreeNode> pAncestor = new ArrayList<>();
        ArrayList<TreeNode> qAncestor = new ArrayList<>();
        findDescendant(root, p, pAncestor);	// p에 해당하는 직계 찾기
        findDescendant(root, q, qAncestor);	// q에 해당하는 직계 찾기

        // 공통 조상 찾기
        TreeNode common = null;
        for(int i=0; i<pAncestor.size(); i++) {
            TreeNode ancestor = pAncestor.get(i);
            for(int j=0; j<qAncestor.size(); j++) {
                if(ancestor == qAncestor.get(j)) {
                    common = ancestor;
                    break;	// 가장 낮은 조상을 반환해야 하므로 찾고 바로 빠져나온다
                }
            }
            if(common != null) break;
        }
        return common;
    }

    public boolean findDescendant(TreeNode root, TreeNode descendant, ArrayList<TreeNode> ancestor) {
        if(root == null) {
            return false;
        }

        if(root == descendant) {
            ancestor.add(descendant);
            return true;
        }

        // 왼쪽 직계 탐색
        if(findDescendant(root.left, descendant, ancestor)) {
            ancestor.add(root); // 해당하는 조상 모두 저장
            return true;
        }

        // 오른쪽 직계 탐색
        if(findDescendant(root.right, descendant, ancestor)) {
            ancestor.add(root);	// 해당하는 조상 모두 저장
            return true;
        }

        return false;
    }
}