Leetcode - 1644. Lowest Common Ancestor of a Binary Tree II

문제

해결 아이디어

기본적으로 236. Lowest Common Ancestor of a Binary Tree 와 코드는 동일. 하지만 q, p노드를 실제로 방문했는지 체크했는지 여부 추가. 따라서 모든 노드를 방문해야함. 그래서 아래 (1) 코드는 양쪽 자식노드 재귀 호출을 마친 이후에 처리해야함. 그 이전에 하면 모든 노드를 방문하지 않고 리턴함.

• 아래 F/U 솔루션도 나중에 살펴보기
  Follow up: Can you find the LCA traversing the tree, without checking nodes existence?

해결

class Solution {
    bool p_cnt = false;
    bool q_cnt = false;
public:
    TreeNode *travel(TreeNode *root, TreeNode *p, TreeNode *q) {
        if (root == NULL)
            return root;
        TreeNode *left = travel(root->left, p, q);
        TreeNode *right = travel(root->right, p, q);
        if (root == p || root == q) { // <-----(1)
            if (root == p)
                p_cnt = true;
            else
                q_cnt = true;
            return root;
        }
        if (left && right)
            return root;
        else if (left && !right)
            return left;
        else if (!left && right)
            return right;
        return NULL;
    }
    TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *p, TreeNode *q) {
        TreeNode *ret = travel(root, p, q);
        if (p_cnt && q_cnt)
            return ret;
        else
            return NULL;
    }
};