면접 필기시험 정리 6: 흔한 면접 프로그래밍 문제

1. 두 갈래 트리 공통 부모 노드 leecode236 귀속 해법:

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root==NULL || root==p||root==q) return root;
        TreeNode *left = lowestCommonAncestor(root->left, p, q);
        TreeNode *right = lowestCommonAncestor(root->right, p, q);
        if(left && right) return root;
        return left?left:right;
    }
};

비귀속 해법, 가장 간단한 것은 노드의 부모 노드와 그 중의 한 경로를 기록하는 것이다.

class Solution(object):
    def lowestCommonAncestor(self, root, p, q):
        """
        :type root: TreeNode
        :type p: TreeNode
        :type q: TreeNode
        :rtype: TreeNode
        """
        stack = [root]
        pair = {root:None}
        while p not in pair or q not in pair:
            node = stack.pop()
            if node.left:
                stack.append(node.left)
                pair[node.left] = node
            if node.right:
                stack.append(node.right)
                pair[node.right] = node
        # p 
        path = set()
        while p :
            path.add(p)
            p = pair[p]
        while q not in path:
            q = pair[q]
        return q 

2. 나무의 중간 순서

// 
void inorderTraversal(TreeNode *root, vector<int> &path)
{
    stack s;
    TreeNode *p = root;
    while(p != NULL || !s.empty())
    {
        while(p != NULL)
        {
            s.push(p);
            p = p->left;
        }
        if(!s.empty())
        {
            p = s.top();
            path.push_back(p->val);
            s.pop();
            p = p->right;
        }
    }
}

귀속판:

void inorder(TreeNode *root, vector<int> &path)
{
    if(root != NULL)
    {
        inorder(root->left, path);
        path.push_back(root->val);
        inorder(root->right, path);
    }
}

3. 두 개의 정렬된 수조의 교집합을 구하는 것은 두 개의 정렬된 수조에 대해 간단하다. 각각 두 개의 바늘을 찾아 수조의 머리를 가리키고 한 개가 다른 것보다 작으면 작은 것으로 이동한다.서로 같으면 저장하고 동시에 두 개의 포인터를 이동합니다

public LinkedList intersection(int[] A, int[] B) {  
    if (A == null || B == null || A.length == 0 || B.length == 0) return null;  
    LinkedList list = new LinkedList();  
    int pointerA = 0;  
    int pointerB = 0;  
    while (pointerA < A.length && pointerB < B.length) {  
        if (A[pointerA] < B[pointerB]) pointerA++;  
        else if (A[pointerA] > B[pointerB]) pointerB++;  
        else {  
            list.add(A[pointerA]);  
            pointerA++;  
            pointerB++;  
        }  
    }  

    return list;  

}  

여러 개의 수조의 경우에도 위의 방법이나 방법을 사용할 수 있다. 먼저 가장 짧은 수조를 찾은 다음에 이 수조의 값을 2분으로 다른 수조에서 찾을 수 있다.