Lowest Common Ancestor of a Binary Tree

236. Lowest Common Ancestor of a Binary Tree

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

Lowest Common Ancestor of a Binary Tree - LeetCode

 

Language: C++

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */


class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        
        if (!root)
            return nullptr;
        else
           return helper(root, p->val, q->val);
        
    }
    
    TreeNode* helper(TreeNode* root, int p, int q) {
        
        if (!root)
            return nullptr;
        
        if (root->val == p || root->val == q)
            return root;
        
        TreeNode* left = helper(root->left, p, q);
        TreeNode* right = helper(root->right, p, q);
        
        if (left && right)
            return root;
        else
            return left ? left : right;
        
    }
};

시도

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        
        // search p, q
        // compare queue
        
    }
    
    queue<TreeNode* > search(TreeNode* root, TreeNode* node) {
        queue<TreeNode*> result;
        
        result.push(root);
        
        TreeNode* temp;
        temp = root;
        
        while (!result.isempty()) {
            result.push(temp);
            if (!searchHelper(temp, node->val))
                break;
            result.push(temp->left);
            if (!searchHelper(temp->left, node->val))
                break;
            result.pop();
            result.push(temp->right);
            if (!searchHelper(temp->right, node->val))
                break;
            result.pop();
            
        }
        
    }
    
    TreeNode* searchHelper(TreeNode* root, int val) {
        
        if (!root)
            return nullptr;
        
        if (root->val == val)
            return root;
        else
            return nullptr;
    
    }
    
};

문제점

첫번째 솔루션 글만 보고 뭔가 재귀로 풀고 찾으면 전달하는 식으로 풀면 되겠다 싶어서 

구조체도 만들고 했었는데 그냥 숫자로 반환해서 2이면 하는 걸로 했어도 되는 거였고(첫번째 솔루션)

솔루션이 세 개 있었는데 코드로도 이해 안되는 게 있어서  discussion 에서 다른 쉬운 해답을 보고

다시 보니까 좀 이해가 되었다

첫번째는 p나 q일 경우 true 를 넘기고 mid 라는 변수를 하나 더 놓아서 현재 노드가 p이거나 q 인지도 같이 본다.

타고타고 올라가서 1 + 1 + mid >= 2 이면 해당 노드가 LCA인 것

두번째는 각 노드의 부모 노드를 다 저장해놓고 비교하는 것이다. -> 원래 이렇게 하고 싶었는데 생각을 못했다.

나는 p의 경로 q의 경로 각각을 찾아서 비교하면서 보려고 했는데

스택이 존재할 때 노드를 도는데, 노드를 돌 때 새로운 자료구조에 각 노드의 자식들의 인덱스에 현재 노드(즉 부모노드) 를 넣어주고

스택에도 넣어주고.. 다 돌면 나와서 

p의 부모 값의 부모 값의 부모 값을 다 새로운 자료구조에 넣고 그 자료구조에서 q의 부모값과 돌아가면서 일치하는 것을 찾는다. 

세번째는 dfs 와 stack 을 이용하는 거.. 각종 상태값도 여러개 있는데 넘겼다.

 

References

https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/discuss/1297527/C%2B%2B-oror-Easy-recursion

 

 

월요일부터 했으니까 지금 6일째인데, 쉬는 날 없이 매일 한다고 생각하니까 지치는데 약속을 하면 꼭 지켜야한다는 게 있어서 하고 있는데 내가 계속 너무 못하니까 흥미가 계속 떨어지는 듯? 하다. 솔루션 봐도 이해안될 때 노트북 덮을까 하다가 다른 해답 찾아서 이해되고, 결국 솔루션도 일부 이해하고 보면 내가 생각했던 게 아예 다른 방향은 아니였었고,, 하루를 보내면 너무 짧아서 하고 싶은 것은 많은데 몇 개를 마치면 하루가 저물기도 하고 나머지를 할 수 있는 체력이 남아있지가 않다. 골절 이후 하루에 걷기를 꾸준히 하려고 노력하고 있는데 근력운동도 조금씩 추가해야될 것 같은..