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 7return 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; } }
No comments:
Post a Comment