알고리즘 스터디 4주차

LeetCode Top Interview Questions [Medium Collection]

Tree And Graph

Binary Tree Inorder Traversal

그냥 중위 순회 하면됨. 재귀 호출
💡 중위 순회 ⇒ 왼쪽 - 중간 - 오른쪽 으로 탐색한다. DFS로 최하위 노드부터 타고 올라오면 된다.

class Solution
{
    void inOrderTraversal(TreeNode *root, vector<int> &v)
    {
        if (root == nullptr)
            return;

        // 왼쪽 서브트리를 중위 순회
        inOrderTraversal(root->left, v);

        // 루트 노드를 방문
        v.push_back(root->val);

        // 오른쪽 서브트리를 중위 순회
        inOrderTraversal(root->right, v);
    }

public:
    vector<int> inorderTraversal(TreeNode *root)
    {
        vector<int> a;
        inOrderTraversal(root, a);

        return a;
    }
};

Binary Tree Zigzag Level Order Traversal

Explore - LeetCode

BFS를 통해 해당 값을 저장한 뒤에 reverse를 통해 돌려줌. 정방향 역방향은, count를 세서 하였다.

class Solution
{
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode *root)
    {
        vector<vector<int>> ans;
        queue<TreeNode *> q;

        if (root != nullptr)
        {
            q.push(root);
        }

        int count = -1;
        while (!q.empty())
        {
            count++;
            ans.push_back({});
            int num = q.size();
            for (int i = 0; i < num; ++i)
            {
                TreeNode *node;
                // 정방향 역방향
                node = q.front();
                q.pop();
                if (node == nullptr)
                {
                    continue;
                }

                ans[count].push_back(node->val);

                if (node->left)
                    q.push(node->left);
                if (node->right)
                    q.push(node->right);
            }

            if (count % 2 == 1)
            {
                reverse(ans[count].begin(), ans[count].end());
            }
        }

        return ans;
    }
};

Construct Binary Tree from Preorder and Inorder Traversal

Explore - LeetCode

전위 순회와 중위 순회가 주어질 경우 리스트를 구성 풀이 방법이 조금 어려웠다. 분할 정복으로 해결.
1. preorder의 1번은 root에 해당. inorder을 기준으로 root의 좌우로 나뉜다.
2. 좌/우 리스트에서 root를 찾은 다음에 해당값을 기준으로 inorder, preorder을 나누고 다시 서치하게 함.
  
  ex)preorder = [3,9,20,15,7], inorder = [9,3,15,20,7] 위와 같은 값이 들어온다.
3. root = 3 (preorder[0])
4. inorder에서 3을 기준으로 좌우로 나눈다.
  1. 좌 = inorder = [9], preorder =[9]
    
    ⇒ root = 9로 종료
  2. 우 = inorder = [15,20,7], preorder = [20,15,7]
    
    ⇒ root = preorder [0] = 20, inorder 에서 20을 기준으로 분할
5. 좌, 우 에서 해당을 기준으로 다시 나눈다.
  
  우측 노드(20 = root) 기준으로
  1. 좌 root = 15
  2. 우 root = 7

class Solution
{
    TreeNode *build(
        const vector<int> &preorder, const int preStart,
        const int inStart, const int inEnd,
        const unordered_map<int, int> &inorderIndex)
    {
        if (inStart > inEnd)
            return nullptr;

        int rootVal = preorder[preStart];
        TreeNode *root = new TreeNode(rootVal);

        const int ValueIndex = inorderIndex.at(rootVal);
        int leftSize = ValueIndex - inStart;

        // 좌/우 서브트리 재귀 호출 idx값을 중심으로 좌우로 나눈다.
        // 좌 [inStart, idx - 1]
        // 우 [idx + 1, inEnd]
        root->left = build(preorder, preStart + 1, inStart, ValueIndex - 1, inorderIndex);
        root->right = build(preorder, preStart + 1 + leftSize, ValueIndex + 1, inEnd, inorderIndex);

        return root;
    }

public:
    TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder)
    {
        // inorder 값 -> 인덱스 맵
        // Find 코스트를 아끼기 위해 unordered_map사용
        unordered_map<int, int> inorderIndex;
        for (int i = 0; i < inorder.size(); i++)
            inorderIndex[inorder[i]] = i;

        return build(preorder, 0, 0, inorder.size() - 1, inorderIndex);
    }
};

PREVIOUS알고리즘 스터디 3주차

NEXT알고리즘 스터디 5주차