Tags » BF's

Generate Parentheses: BFS, DFS

这个题目虽然简单,但是有两种做法。一种recursive DFS,一种queue的iterative BFS

    public List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<String>();
        gen(result, 0, 0, n, "");
        return result;
    }
    private void gen(List<String> result, int left, int right, int n, String tmp) {
        if (left == right && left == n)
            result.add(tmp);
        else if (left >= right && left <= n ){
            gen(result, left, right+1, n, tmp + ")");
            gen(result, left+1, right, n, tmp +"(");
        }
    }
… 126 more words

Word Ladder I, II

Word Ladder I
Shortest Path Length – BFS

    public int ladderLength(String start, String end, Set<String> dict) {
        dict.add(end);
        Queue<String> words = new LinkedList<String>();
        Queue<Integer> lens = new LinkedList<Integer>();
        Set<String> visited = new HashSet<String>();
        words.offer(start);
        lens.offer(1);
        visited.add(start);
        while (!words.isEmpty()) {
            String word = words.poll();
            int len = lens.poll();
            if (word.equals(end))
                return len;
            for (int i = 0; i < word.length(); i++) {
                char c = word.charAt(i);
                for (char j = 'a'; j <= 'z'; j++) {
                    if (j == c) continue;
                    char[] str = word.toCharArray();
                    str[i] = j;
                    String newStr = new String(str);
                    if (!visited.contains(newStr) &&dict.contains(newStr)) {
                        words.offer(newStr);
                        lens.offer(len+1);
                        visited.add(newStr);
                    }
                }
            }
        }
        return 0;
	}
… 288 more words

Deep Copy Graph

bfs
另外需要一个map来保存新创建的vertex。

    public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
		if (node == null)
			return node;
		Queue<UndirectedGraphNode> queue = new LinkedList<UndirectedGraphNode>();
		Map<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<UndirectedGraphNode, UndirectedGraphNode>();

		UndirectedGraphNode root = new UndirectedGraphNode(node.label);
		map.put(node, root);

		queue.add(node);
		
		while (!queue.isEmpty()) {
			UndirectedGraphNode cur = queue.poll();
			
			for (UndirectedGraphNode n : cur.neighbors) {
				if(!map.containsKey(n)) {
					UndirectedGraphNode newNode = new UndirectedGraphNode(n.label);
					queue.add(n);
					map.put(n, newNode);
				}
				map.get(cur).neighbors.add(map.get(n));
			}
		}
		return root;
	}

Binary Tree Level Order Traversal II

Iterative BFS

    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        if (null != root)
            queue.offer(root);
        int countCur = 1, countNext = 0;
        List<Integer> layerRes = new ArrayList<Integer>();
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            layerRes.add(node.val);
            if (null != node.left) {
                queue.offer(node.left);
                countNext++;
            }
            if (null != node.right) {
                queue.offer(node.right);
                countNext++;
            }
            if (countCur == layerRes.size()) {
                result.add(new ArrayList<Integer>(layerRes));
                layerRes.clear();
                countCur = countNext;
                countNext = 0;
            }
        }
        Collections.reverse(result);
        return result;
    }

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}, 111 more words

Leetcode

Binary Tree Zigzag Level Order Traversal

Given a binary tree, return the zigzag level order traversal of its nodes’ values. (ie, from left to right, then right to left for the next level and alternate between). 143 more words

Leetcode

Binary Tree Level Order Traversal II

Given a binary tree, return the bottom-up level order traversal of its nodes’ values. (ie, from left to right, level by level from leaf to root). 157 more words

Leetcode