online advertising

Tuesday, December 1, 2015

LeetCode OJ - Populating Next Right Pointers in Each Node II

Problem: 

Please find the problem here.

Solution:

If we are allowed to use more space, then a simple BFS would have solved the problem, the twist in this problem is the requirement to use constant space.

Well, except the space we already occupied already! We have a free linked list to use, the next pointers of the visited nodes, and we have to populate them anyway as output!

Think like induction, layer by layer.

The next of the root is easy, it has to be NULL. The leftmost node on this layer is obviously root.

Now we are trying to build the next pointers of the $ n $ layer, assuming we know the leftmost node of the $ n - 1 $ layer, and that the next pointers are all set correctly there.

Then we just walk the $ n - 1 $ layer from left to right, if we see any child, we just set the child's next pointer correctly, keep track of the first node seen as the leftmost node, and that's it!

By induction we will be able to build the whole tree - a virtual node is conveniently used to reduce the number of cases to deal with when building the next layer nodes.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/populating-next-right-pointers-in-each-node-ii/

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

using namespace std;

namespace _LEET_POPULATING_NEXT_RIGHT_POINTERS_IN_EACH_NODE_II
{
    struct TreeLinkNode
    {
        int val;
        TreeLinkNode *left, *right, *next;
        TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
    };

    class Solution
    {
    public:
        void connect(TreeLinkNode *root)
        {
            if (root == NULL)
            {
                return;
            }

            root->next = NULL;

            TreeLinkNode virtualNode(10086);
            virtualNode.next = root;

            while (virtualNode.next != NULL)
            {
                TreeLinkNode* currentLayerCursor = virtualNode.next;
                TreeLinkNode* nextLayerEnds = &virtualNode;
                nextLayerEnds->next = NULL;
                while (currentLayerCursor != NULL)
                {
                    if (currentLayerCursor->left != NULL)
                    {
                        nextLayerEnds->next = currentLayerCursor->left;
                        nextLayerEnds = nextLayerEnds->next;
                    }
                    if (currentLayerCursor->right != NULL)
                    {
                        nextLayerEnds->next = currentLayerCursor->right;
                        nextLayerEnds = nextLayerEnds->next;
                    }
                    currentLayerCursor = currentLayerCursor->next;
                }
            }
        }
    };
};

using namespace _LEET_POPULATING_NEXT_RIGHT_POINTERS_IN_EACH_NODE_II;

int LEET_POPULATING_NEXT_RIGHT_POINTERS_IN_EACH_NODE_II()
{
    TreeLinkNode a(1);
    TreeLinkNode b(2);
    TreeLinkNode c(3);
    TreeLinkNode d(4);
    TreeLinkNode e(5);
    TreeLinkNode g(7);
    a.left = &b;
    a.right = &c;
    b.left = &d;
    b.right = &e;
    c.left = NULL;
    c.right = &g;
    d.left = NULL;
    d.right = NULL;
    e.left = NULL;
    e.right = NULL;
    g.left = NULL;
    g.right = NULL;
    Solution solution;
    solution.connect(&a);
    cout << ((a.next == NULL) ? "Yes" : "No") << endl;
    cout << ((b.next == &c) ? "Yes" : "No") << endl;
    cout << ((c.next == NULL) ? "Yes" : "No") << endl;
    cout << ((d.next == &e) ? "Yes" : "No") << endl;
    cout << ((e.next == &g) ? "Yes" : "No") << endl;
    cout << ((g.next == NULL) ? "Yes" : "No") << endl;
    return 0;
}

No comments :

Post a Comment