.leetcode(236. Lowest Common Ancestor of a Binary Tree)

문제

https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/

문제 풀기 전

1. 일단 두 노드를 찾는다.
2. 두 노드의 부모를 비교하면서 제일 가까운 부모를 찾는다.
3. 이렇게 해도 logN 으로 걸릴것이다.

직접 푼 풀이

소요시간: 41분(22:36 ~ 11:17)

class Solution {
    private boolean found = false;
    private LinkedList<TreeNode> gstack;

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        find(root, p, new LinkedList<>());
        LinkedList<TreeNode> pQueue = gstack;
        pQueue.push(p);

        found = false;
        find(root, q, new LinkedList<>());
        LinkedList<TreeNode> qQueue = gstack;
        qQueue.push(q);

        TreeNode ret = null;
        while (!pQueue.isEmpty() || !pQueue.isEmpty()) {
            TreeNode pp = pQueue.pollLast();
            TreeNode qq = qQueue.pollLast();
            if (pp == qq) {
                ret = pp;
            } else {
                break;
            }
        }

        return ret;
    }

    private void find(TreeNode root, TreeNode target, LinkedList<TreeNode> stack) {
        if (root == null) {
            return;
        }

        if (found) {
            return;
        }

        if (root.val == target.val) {
            found = true;
            gstack = stack;
            return;
        }

        stack.push(root);
        find(root.left, target, stack);
        find(root.right, target, stack);
        if (!found) {
            stack.pop();
        }
    }
}

느낀점

1. 글로벌 변수에 found변수 쓴거면 거의 필살기를 다 써서 풀었다.
2. 이론은 알겠는데 트리에서 부모를 찾는게 참 어렵구나를 알게되었다.
3. 다시 문제풀이를 이해한 것은 이는 부모를 찾는게 아니라 subTree의 값을 어떤값을 올리고 그 값을 어떻게 판단할 것인가로 봐야겠다. 즉 리턴으로 판단할 수 있게끔 데이터를 정하고 그 데이터를 어떻게 판단할지를 고민하는 문제였다. 이 경우 post-order방식으로 판단해서 결과를 올리는 것을 볼 수 있다. 이렇게하면 O(n)속도로 풀 수 있다.

솔루션 공부 후 추가로 푼 풀이

class Solution {
    private TreeNode ret;
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        recursion(root, p, q);
        return ret;
    }

    private boolean recursion(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return false;
        }

        int left = recursion(root.left, p, q) ? 1 : 0;
        int right = recursion(root.right, p, q) ? 1 : 0;
        int mid = (root == p || root == q) ? 1: 0;

        if (mid + left + right >=2) {
            ret = root;
            return true;
        }

        return (mid + left + right > 0);
    }
}

누적되는 알고리즘 접근 설명서

2021/01/09 - [알고리즘 풀이] - .leetcode(알고리즘 문제풀이 접근)

나중에다시한번

• 제대로 다시 풀어보자