235. Lowest Common Ancestor of a Binary Search Tree

링크

 

참고한 코드

 

풀이 코드

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 * 
 * 1. 문제 해석하기
 * 이진 탐색 트리의 가장 낮은 공통 조상을 찾아달라는 문제입니다.
 * 2. 문제 풀이 방법
 * TreeNode를 따라 내려간다.
 * left의 val 혹은 right의 val이 p혹은 q일 경우 그 다음 값도 확인한다.
 * 조상이 p 혹은 q 인 경우도 있기 때문에 해당 경우도 고려한다.
 * 같은 숫자를 가진 노드는 없다.
 * 
 * p의 조상 목록과 q의 조상 목록을 찾는다. (가장 처음은 root가 되고 가장 마지막이 lowest할 것)
 * 마지막부터 조상 목록 비교 후 같은 조상을 반환한다.
 */

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        
        List<TreeNode> list1 = new ArrayList<>();
        List<TreeNode> list2 = new ArrayList<>();
        
        boolean left = find(root, list1, p);
        boolean right = find(root, list2, q);

        TreeNode result = findLCA(list1, list2);

        return result;

    }

    public TreeNode findLCA(List<TreeNode> list1, List<TreeNode> list2) {
        int i = 0;
        
        for(i = 0; i < list1.size() && i < list2.size(); i++) {
            if (list1.get(i).val != list2.get(i).val) {
                break;
            }
        }

        return list1.get(i - 1);
    }

    public boolean find(TreeNode root, List<TreeNode> list, TreeNode a) {
        if (root == null) {
            return false;
        }
        
        list.add(root);
        if (root.val == a.val || find(root.left, list, a) || find(root.right, list, a)) {
            return true;
        }

        list.remove(list.size() - 1);
        
        return false;
    }
}

 

조상 목록을 찾아서 비교해야지! 까지는 생각해냈는데

목록을 어떻게 찾아내야하는지, 가지고온 목록을 어떻게 비교해야하는지 하는 부분에서 막혀서 한참 고민하다가 풀이 참고해서 풀었다.

 

아직 많이 부족한 것 같다.