Posts Tagged ‘bfs’
树的dfs变形，还是两个list来回倒。但是这题上来就写还不行，真心得在纸上画一画才能看出来规律。一开始觉得keep一个boolean，正常顺序就加后面，逆序就加前面呗，但是没注意到parent其实很可能已经不是原来顺序的了。画个四层的树就能看出来咋回事了。还有一个小bug就是最开始的boolean reverse应该是true，因为他代表了“parent下面一层要什么顺序”，而不是parent本身是什么顺序。所以还是，变量的物理意义一定要搞清再写！
public ArrayList<ArrayList<Integer>> zigzagLevelOrder(TreeNode root) {
ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
if (root == null)
return result;
ArrayList<TreeNode> parents = new ArrayList<TreeNode>();
boolean reverse = true;//first children line is reversed
parents.add(root);
while (!parents.isEmpty()) {
ArrayList<TreeNode> children = new ArrayList<TreeNode>();
for (int i = parents.size() - 1; i >= 0; i--) {
TreeNode parent = parents.get(i);
if (!reverse) {// the children list wants to be normal order
if (parent.left != null)
children.add(parent.left);
if (parent.right != null)
children.add(parent.right);
} else { //the children wants to be right to left
if (parent.right != null)
children.add(parent.right);
if (parent.left != null)
children.add(parent.left);
}
}
result.add(convertToIntegerList(parents));
reverse = !reverse;
parents = children;
}
return result;
}
[leetcode] Clone Graph | 克隆无向图
Posted on: October 8, 2013
倒是20分钟写出来了bugfree，比较喜欢这种利用data structure的题，感觉试一试总能想出来。
这个题就是基本BFS，要点是生成新节点的同时，怎么把新节点和其他新节点连起来呢？这就需要一个新旧节点对应map，每次生成新节点A’，要把dequeue的这个parent B对应的新节点B’和当前作为child的新节点A’连起来。注意单向连就行了(B’->A)’，因为下次把A当作root的时候，还会经历B作为child，这时再A’->B’。
public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
if (node == null)
return null;
Queue<UndirectedGraphNode> q = new LinkedList<UndirectedGraphNode>();
Map<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<UndirectedGraphNode, UndirectedGraphNode>();
enqueueAndClone(q, node, map);
while (!q.isEmpty()) {
UndirectedGraphNode parent = q.poll();
for (UndirectedGraphNode child : parent.neighbors) {
if (!map.containsKey(child))
enqueueAndClone(q, child, map);
map.get(parent).neighbors.add(map.get(child));//不管是否visit过，都要单向连接
}
}
return map.get(node);
}
private void enqueueAndClone(Queue<UndirectedGraphNode> q, UndirectedGraphNode node, Map<UndirectedGraphNode, UndirectedGraphNode> map) {
q.add(node);
UndirectedGraphNode newNode = new UndirectedGraphNode(node.label);
map.put(node, newNode);
}
[leetcode] Populating Next Right Pointers in Each Node II | 把二叉树横向next节点populate了
Posted on: August 9, 2013
很简单的题，因为熟悉了用两个list做tree的bfs，所以这里一层一层iterate就行了，上一层反正已经做完了，所以能直接横着遍历上一层，把下一层populate了。轻松过。
Lexi's Leetcode solutions 