Day 46, ##, #102 Copy List with Random Pointer, Binary Tree Level Order Traversal

Copy List with Random Pointer
A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.
Return a deep copy of the list.
------------------------------------------
The key point here is to set a direct link between the original node and its duplicate. So during the second iteration, the new/duplicate *next and *random nodes can be traced by their original nodes.

Besides using a map, the link can be implemented by attaching each duplicate right after to its original node in the linked list.

/**
 * Definition for singly-linked list with a random pointer.
 * struct RandomListNode {
 *     int label;
 *     RandomListNode *next, *random;
 *     RandomListNode(int x) : label(x), next(NULL), random(NULL) {}
 * };
 */
class Solution {
public:
    RandomListNode *copyRandomList(RandomListNode *head) {
        // Note: The Solution object is instantiated only once and is reused by each test case.
        if (head == NULL) return NULL;
        RandomListNode *ret = head, *itr = head;
        unordered_map<RandomListNode*,RandomListNode*> mapping;
        // set up the relationship between orignial and its duplicates
        while (itr != NULL) {
            RandomListNode *dup = new RandomListNode(itr->label);
            mapping[itr] = dup;
            itr = itr->next;
        }
        itr = head;
        // second iteration, set up *next and *random for duplicates
        while (itr != NULL) {
            RandomListNode *dup = mapping[itr];
            dup->next = mapping[itr->next];
            dup->random = mapping[itr->random];
            itr= itr->next;
        }
        return mapping[head];
    }
};

Binary Tree Level Order Traversal
Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).
For example:
Given binary tree {3,9,20,#,#,15,7},

    3
   / \
  9  20
    /  \
   15   7

return its level order traversal as:

[
  [3],
  [9,20],
  [15,7]
]

--------------------------------------------
Solution #1 iterativ
Typical breadth first search, keep two queues to track all the nodes, use an integer to determine which should be used for current iteration
Challenge: use DFS to solve this 
check #107 Binary Tree Level Order Traversal II for DFS recursive solution

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    void foo (queue<TreeNode*>& cur, queue<TreeNode*>& next, vector<int>& level) {
        while (!cur.empty()) {
            TreeNode* current = cur.front();
            cur.pop();
            level.push_back(current->val);
            if (current->left != NULL) {
                next.push(current->left);
            }
            if (current->right != NULL) {
                next.push(current->right);
            }
        }
    }

    vector<vector<int> > levelOrder(TreeNode *root) {
        // Note: The Solution object is instantiated only once and is reused by each test case.
        queue<TreeNode*> que,p;
        vector<vector<int> > ret;
        if (root == NULL) return ret;
        int levelCount = 0;
        que.push(root);
        while (!que.empty() || !p.empty()) {
            vector<int> level;
            if (levelCount % 2 == 0) {
                foo(que,p,level);
            }else {
                foo(p,que,level);
            }
            ret.push_back(level);
            levelCount++;
        }
        return ret;
    }
};

Update on Sep-24-2014 
refactoried

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    void traverse(vector<vector<int> > &rt, queue<TreeNode*> &q1, queue<TreeNode*> &q2) {
        vector<int> v;
        while (!q1.empty()) {
            TreeNode * top = q1.front();
            q1.pop();
            v.push_back(top->val);
            if (top->left != NULL) q2.push(top->left);
            if (top->right != NULL) q2.push(top->right);
            
        }
        
        rt.push_back(v);
    }

    vector<vector<int> > levelOrder(TreeNode *root) {
        vector<vector<int> > rt;
        if (root == NULL) return rt;
        queue<TreeNode*> q1;
        queue<TreeNode*> q2;
        q1.push(root);
        
        while (!q1.empty() || !q2.empty()) {
            if (!q1.empty()) {
                traverse(rt,q1,q2);
            }
            if (!q2.empty()) {
                traverse(rt,q2,q1);
            }
        }
        
        return rt;
    }
};

Update on Sep-26-2014 
DFS

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    void dfs(vector<vector<int> > &rt, int level, TreeNode *root) {
        if (root == NULL) return;
        
        if (rt.size() < level) {
            vector<int> v;
            rt.push_back(v);
        }
        
        rt[level - 1].push_back(root->val);
        dfs(rt,level + 1, root->left);
        dfs(rt,level + 1, root->right);
        
    }

    vector<vector<int> > levelOrder(TreeNode *root) {
        vector<vector<int> > rt;
        dfs(rt,1,root);
        return rt;
    }
};

Java, updated on Jul-30th-2018

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> rt = new ArrayList<>();
        if (root == null) return rt;
        
        Queue<TreeNode> que = new LinkedList<>();
        que.add(root);
        int size = 1;
        rt.add(new ArrayList<>());
        
        while (!que.isEmpty()) {
            if (size == 0) {
                rt.add(new ArrayList<>());
                size = que.size();
            }
            
            size--;
            TreeNode node = que.poll();
            rt.get(rt.size() - 1).add(node.val); 
            if (node.left != null) que.add(node.left);
            if (node.right != null) que.add(node.right);
        }
        
        return rt;
    }
}