Monday, September 28, 2015

LeetCode OJ - Flatten Binary Tree to Linked List

Problem:

Please find the problem here.

Solution:

I spent some time thinking about this one.

First, note that, the signature do not allow a return, which means the root of the tree node must be unchanged. That's calls for pre-order.

Next, if we do a pre-order traversal, and then modify the tree at the same time, we are done.

In order to stitch the list together, I need the end of the list, that's why I introduced a helper function for that purpose, it returns the end of the list of the subtree we are processing.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/flatten-binary-tree-to-linked-list/

#include "LEET_FLATTEN_BINARY_TREE_TO_LINKED_LIST.h"
#include <map>
#include <iostream>
#include <sstream>
#include <vector>
#include <string>

using namespace std;

namespace _LEET_FLATTEN_BINARY_TREE_TO_LINKED_LIST
{
    struct TreeNode
    {
        int val;
        TreeNode *left;
        TreeNode *right;
        TreeNode(int x) : val(x), left(NULL), right(NULL) {}
    };
    class Solution
    {
        TreeNode* flattenWithLast(TreeNode* root)
        {
            TreeNode* left = root->left;
            TreeNode* right = root->right;
            root->left = NULL;
            root->right = NULL;
            TreeNode* last = root;
            if (left != NULL)
            {
                last->right = left;
                last = flattenWithLast(left);
            }
            if (right != NULL)
            {
                last->right = right;
                last = flattenWithLast(right);
            }
            return last;
        }
    public:
        void flatten(TreeNode* root) {
            if (root == NULL)
            {
                return;
            }
            flattenWithLast(root);
        }
    };
};

using namespace _LEET_FLATTEN_BINARY_TREE_TO_LINKED_LIST;

int LEET_FLATTEN_BINARY_TREE_TO_LINKED_LIST()
{
    Solution solution;
    TreeNode a(1);
    TreeNode b(2);
    TreeNode c(3);
    TreeNode d(4);
    TreeNode e(5);
    TreeNode f(6);
    a.left = &b;
    b.left = &c;
    b.right = &d;
    a.right = &e;
    e.right = &f;
    solution.flatten(&a);
    TreeNode* curr = &a;
    while (curr != NULL)
    {
        cout << curr->val;
        curr = curr->right;
    }
    cout << endl;
    return 0;
}

No comments :

Post a Comment