算法训练——深度优先和广度优先

深度优先和广度优先算法

深度递归算法重要的是的缺陷是的就是内存的使用大。容易产生的超过内存的情况。

 深度优先遍历就是的递归算法的一种。

// Java
public void DFS(int level, int param) { 
  // terminator 
  if (level > MAX_LEVEL) { 
    // process result 
    return; 
  }
  // process current logic 
  process(level, param); 
  // drill down 
  recur( level: level + 1, newParam); 
  // restore current status 
 

广度优先遍历就是的while +queue这样的方式来解决这样。

/** 广度遍历代码模板 */
public class TestBFS {
  public List BFS(TreeNode root) {
      // 如果节点为空
      if (root == null) {
          return null;
      }
      List result = new ArrayList();
      Queue queue = new LinkedList();
      queue.add(root);
      while (!queue.isEmpty()) {
          int size = queue.size();
          List level = new ArrayList();
          for (int i = 0; i < size; i++) {
              TreeNode curNode = queue.poll();
              if (curNode == null) {
                  continue;
              }
              level.add(curNode.val);
              queue.add(curNode.left);
              queue.add(curNode.right);
          }
          if (!level.isEmpty()) {
              result.add(level);
          }
      }
      return result;
  }
}

实战的题目

二叉树的遍历的相关问题

102. 二叉树的层序遍历

433. 最小基因变化

22. 括号生成

200. 岛屿数量

 @Test
    public void test() {
        String string = minString(new String[]{"abc", "de"});
        System.out.println("*************");
        System.out.println(string);
    }

    public String minString(String[] strs) {
        if (strs.length == 0) {
            return null;
        }
        ArrayList lists = new ArrayList();
        ArrayList list = new ArrayList();
        boolean[] vis = new boolean[strs.length];
        dfs(strs, list, lists, vis);

        ArrayList ans = new ArrayList();
        for (ArrayList list1 : lists) {
            String res = "";
            for (String s : list1) {
                res += s;
            }
            ans.add(res);
        }
        Collections.sort(ans);
        return ans.get(0);
    }

    private void dfs(String[] strs, ArrayList list, ArrayList lists, boolean[] vis) {
        if (list.size() == strs.length) {
            lists.add((ArrayList) list.clone());
        }
        for (int i = 0; i < strs.length; i++) {
            if (!vis[i]) {
                list.add(strs[i]);
                vis[i] = true;
                dfs(strs, list, lists, vis);
                list.remove(list.size() - 1);
                vis[i] = false;
            }
        }
    }