[Binary Tree][Medium] 114. Flatten Binary Tree to Linked List

Q. 주어진 binary tree를 linked list와 같은 flatten 하여라. 

 이때 tree를 pre-order 순회한 결과를 flatten 하여라. 

 

Solution

 Tree 에 대한 이해가 충분하면 역시 어렵지 않으리라 생각된다. 

 우선 tree를 pre order 순회하면서 그 결과를 특정 버퍼에 넣고, 

 버퍼를 순서대로 순회하면서 오른쪽 leaf 에만 child 를 attach 한다. 

 

 로직대로 코드를 만들어 본다. 

 

 

    // vector를 순회하며 우측에만 child를 attach 한다.
    TreeNode* build_flatten(vector<TreeNode*>& vNodes, int& idx)
    {
        if (idx >= vNodes.size())
            return NULL;

        TreeNode* node = vNodes[idx++];
        node->left = NULL;
        node->right = build_flatten(vNodes, idx);
        return node;
    }
    void flatten_preorder(TreeNode* node, vector<TreeNode*>& vNodes)
    {
        if (node == NULL)	return;
        vNodes.push_back(node);
        if (node->left != NULL)		flatten_preorder(node->left, vNodes);
        if (node->right != NULL)	flatten_preorder(node->right, vNodes);
    }
public:
    void flatten(TreeNode* root) 
    {
        if(root == NULL)    return;

        vector<TreeNode*> vNodes;
        flatten_preorder(root, vNodes);

        int idx = 0;
        build_flatten(vNodes, idx);
    }

 

적절한 결과를 얻었다.