Lexi's Leetcode solutions

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;
}
Advertisements
Tags: ,

倒是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);
}

很简单的题,因为熟悉了用两个list做tree的bfs,所以这里一层一层iterate就行了,上一层反正已经做完了,所以能直接横着遍历上一层,把下一层populate了。轻松过。

Tags: , ,