BFS & Dijkstra's & DFS(backtracking)

搜索／遍历 算法 --> all possible solutions

BFS:

Breadth First Search: 遍历层，宽度优先; Queue

  1. neighbors这层不遍历完，neighbors‘neighbors绝对不会遍历

  2. steps

  3. 石头砸湖 --> 救护车救人

BFS在tree中的使用

  • level order traverse, 右边进，左边出，use Queue

  • 分层体现的方案

    • 两个queue

    • size

Using queue for BFS

  1. push root

  2. expand / queue.poll() / visit / print / add to result

  3. generate(convert) neighbours and push into queue

Q1L102 Binary Tree Level Order Traversal

  1. level order traversal 不分层打印 加上null

  2. 分层打印

public void levelOrderTraversal(TreeNode root){
    if(root == null) return;
    Queue<TreeNode> que = new LinkedList<>();
    que.offer(root);
    while(!que.isEmpty()){
        TreeNode pollNode = que.poll();
        System.out.println(pollNode.value);
        if(pollNode.left != null){
            que.offer(pollNode.left);
        }
        if(pollNode.right != null){
            que.offer(pollNode.right);
        }
    }
}
public List<List<Integer>> levelOrderTravers(TreeNode root){
    List<List<Integer>> result = new ArrayList<List<Integer>>();
    if(root == null){
        return result;
    }
    Queue<TreeNode> queue = new LinkedList<TreeNode>();
    queue.offer(root);
    while(!queue.isEmpty()){
        int size = queue.size();
        List<Integer> list = new ArrayList<>();
        for(int i = 0; i < size; i++){
            TreeNode node = queue.poll();
            list.add(node.val);
            if(node.left != null){
                queue.offer(node.left);
            }
            if(node.right != null){
                queue.offer(node.right);
            }
        }
        result.add(list); //分层的位置所在
    }
    //Collections.reverse(res);
    return result;
}

Q1.1 do it by DFS

左边尽量靠下；

  1. dfs carray level information

  2. the relationship that level to list

    1. key is the level, list is value

Q1.2 L107 from bottom to top

use reverse function

Q1.3 L314

纵向，需要知道第几个colom, use BFS寻找colom的对应关系，use hashmap

Q1.4 level order Traversal from right to left

print right first

Q1.5 leaf nodes order traversal

height,到具有相同height值的一一对应关系

Q1.6 seeing from left or right

Q2 L103 Binary Tree ZigZag Level Order Traversal

这道题是一行一行打印，so use bfs

Q2.1 能被整除的行，从左向右打印

S1: using queue

1.1 using one queue with reverse();

1.2 using stack + stack

public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
    List<List<Integer>> res = new ArrayList<List<Integer>>();
    Queue<TreeNode> queue = new LinkedList<>();
    if(root == null){ return res; }
    Stack<TreeNode> s1 = new Stack<>();
    Stack<TreeNode> s2 = new Stack<>();
    s1.add(root);
    while(!s1.isEmpty()||!s2.isEmpty()){
        List<Integer> list = new ArrayList<>();
        if(!s1.isEmpty()){
            while(!s1.isEmpty()){
                TreeNode node = s1.pop();
                list.add(node.val);
                if(node.left != null){ 
                    s2.push(node.left); 
                    }
                if(node.right != null){ 
                s2.push(node.right); 
                }
            }   
        }else{
            while(!s2.isEmpty()){
                TreeNode node = s2.pop();
                list.add(node.val);
                if(node.right != null) {
                    s1.push(node.right); 
                    }
               if(node.left != null) { 
                   s1.push(node.left); }
               }
            }
            res.add(list);
        }
        return res;
    }

S2: 左进右出 and 右进左出 deque(stack, queue)

  • offerFirst() offerLast() pollFirst() pollLast()

  • 只写offer，isofferLast，只写poll，pollFirst

  • 怎么标定哪一个需要从右到左？

    • boolean flag = true; flag = ! flag;

    • int flag = 0; flag = 1- flag

    • int level; level %2 == 0; level++

      • it is universal

      • but it is level++ --> level%= 2

public List<List<Integer> zigZagTraversal(TreeNode root){
    List<List<Integer>> ans = new ArrayList<List<Integer>>();
    if(root == null) return null;
    Deque<TreeNode> deque = new LinkedList<TreeNode.()
    deque.offerLast(root);
    boolean flag = false;
    while(!deque.isEmpty()){
        int size = deque.size();
        List<Integer> list = new ArrayList<>();
        for(int i =  0; i < size; i++){
           if(flag == false){
               TreeNode node = queue.pollFist();
               if(node.left != null){
                   list.offerLast(node.left);
               }
               if(node.right != null){
                   list.offerLast(node.right);
               }
           }else{
               if(flag != false){
               TreeNode node = queue.pollLast();
               if(node.left != null){
                   list.offerFirst(node.left);
               }
               if(node.right != null){
                   list.offerFirst(node.right);
               }
           }
        }
        flag = ! flag;
        ans.add(list);
    }
    return ans;
}

Q2.2 what if print out null

public void levelOrderTraversal(TreeNode root){
    if(root == null) return;
    Queue<TreeNode> que = new LinkedList<>();
    que.offer(root);
    while(!que.isEmpty()){
        TreeNode pollNode = que.poll();
        //if(pollNode == null){
            System.out.println("null");
        }
        else{
            System.out.println(pollNode.value);
        
            que.offer(pollNode.left);
            que.offer(pollNode.right);
        }
    }
}

Q3 Validate a Complete Binary Tree

  • 如果左边是null，右边也必须是null rather than a value

S1: manually add a mark to indicate null

public boolean levelOrderTraversal(TreeNode root){
    if(root == null) return true;
    Queue<TreeNode> que = new LinkedList<>();
    que.offer(root);
    boolean flag = false;
    while(!que.isEmpty()){
        TreeNode pollNode = que.poll();
        if(pollNode == null){
            flag = true;
        }
        else{
            if(flag == true) return false;
            que.offer(pollNode.left);
            que.offer(pollNode.right);
        }
    }
    return true;
}

S2:遍历parent,if children have one null, the following parent should all null children

public boolean levelOrderTraversal(TreeNode root){
    if(root == null) return;
    Queue<TreeNode> que = new LinkedList<>();
    que.offer(root);
    boolean flag = false;
    while(!que.isEmpty()){
        TreeNode pollNode = que.poll();
        System.out.println(pollNode.value);
        if(pollNode.left != null){
            que.offer(pollNode.left);
        }else{
            flag = true;
        }
        if(pollNode.right != null){
            if(flag == null) return false;
            que.offer(pollNode.right);
        }else{
            flag = true;
        }
    }
    return true;
}

S3: math size

Q4 L785 Check whether a given graph is Bipartite or not

node's neighbor, use covering way to determine two different group

Q5 Graph Traversal -->Matrix

  • 5.1 L286 shortest Path in Simple Graph

  • 5.2 Graph BFS vs Tree BFS

Dijkstra's Algorithm

Dijkstra Algorithm is used to find the shortest path from one node to any other node in graph.

带权重(with weight)的BFS --> Best FIrst Search

Data Structure: Heap --> customize a queue

Q1 how to find the shortest path from node a to node b

public void dijstra(GraphNode root){
    // assume connected undirected graph
    PriorityQueue<GraphNode>pq = new PriorityQueue<>();
    Set(GraphNode) set = new HashSet<>();
    pq.offer();
    while(!pq.isEmpty()){
        //expand poll();
        //find neis generate put into heap
    }
}

class GraphNode{
    int value;
    boolean visited;//false
    int distant;//+inf
    
    List<Pair> neis : Pair{GraphNode weight} Hashmap(prefer)
    
    GraphNode(){
    
    }
}

public void dijkstra(GraphNode start){ //below the comparator is a interface
    Queue<Cell> minHeap = new PriorityQueue<Cell>(k, new Comparator<Cell>(){
    @Override // lambda expression(c1, c2) -> {c1.distance - c2.distance}
        public int compare(Cell c1, Cell c2){
        return c1.distance - c2.distance; // minHeap
        }
    })
    //HashSet
}

Heap: offer() poll() peek()

Q2 L378 find the kth smallest elements VS Matrix find path or find path sum

  • clarify:

    • kth smallest: 从小到大kth(smallest to largest)，or从大到小kth

    • sorted?

    • any repete?

  • start: matrix[0][0]

  • Expand/Generate: expand[i][j] --> [i+1][j][i][j+1]

  • Termination: kth element, heap poll() kth time

  • Deduplicate:boolean[][] Matrix, --> boolean[][], HashSet

  • int[2] List<Integer> Point

  • Hashset<key = <i, j> --> i * matrix[0].length + j vs j * matrix.length + i

DFS / Recursion / Backtracing

所有的搜索遍历问题都使用DFS

How to solve DFS problem? Recursion / Search tree

  1. how many and what is the meaning of each level?

  2. how many brachs for each level ? left right

  3. where is the answer? leaf nodes or all nodes

Q1 L78 Subsets No.15 1:05:00

S1: DFS1

  • 加答案时是deep copy 而不是shallow copy

  • str + arr[i], no backtracking needed

private void dfs(char[] array, int index, StringBuilder sb, List<String> res){
    res.add(sb.toString());// deep copy
    for(int i = index; i< array.lenght; i++){
        sb.append(array[i]);
        dfs(array, i+1 , sb, res);
        //
        sb.deleteCharAt(sb.length()-1); //backtracing
    }
    
}

S2: DFS2: 每个character在不在我的搜索树subset当中

private void dfs(char[] array, int index, StringBuilder sb, List<String> result){
    //if we decide on all positions
    // we have a complete subset, all subset locate on the leaf node
    if(index == array.lenght){
        result.add(sb.roString()); // deep copy arr.clone()
        return;
    }
    //case1: add character at index;
    sb.append(array[index]);
    dfs(array,sb,index+1,result);
    
    //wall
    //remove the added character when backtracing to the upper level
    sb.deleteCharAt(sb.length()-1); //backtracing
    
    //case2: NOT add character at index
    dfs(array, sb, index+1, result);
    //wall
    
}

S3: BFS2

S4: BFS1 similiar BFS by Queue

Q2 L22 Generate Parentheses 2:20:00

2.1L20 Valid Parentheses

private void dfs(int n, int l, int r, StringBuilder sb, List<String> sb){
    //base case
    if(l + r == 2*n){
        res.add(sb.toString());
        return;
    }
    if(l < n){
        sb.append('(');
        DFS(n, l+1, r, result, sb);
        sb.deleteCharAt(sb.length()-1);
    }
    if(r < l){
        sb.append(')');
        DFS(n, l, r+1, result,sb);
        sb.deleteCharAt(sb.length()-1);
    }
}
private void dfs(int n, int l, int r, StringBuilder sb, List<String> sb){
    //success
    if(left == n && right == n){
        res.add(sb.toString());
        return
    }
    //failure
    if(left > n ||left > right){
        return;
    }    
   // '('
    sb.append('(');
    DFS(n, l+1, r, result, sb);
    sb.deleteCharAt(sb.length()-1);
  
    //')'
    sb.append(')');
    DFS(n, l, r+1, result,sb);
    sb.deleteCharAt(sb.length()-1);
   
}

Q3 L77 Combinations

Q3.1 coins sum up to target

coins[]: 25, 10, 5, 1

target: 100

一共有四层，每层每个币种取几次，每次分几个char（100／25 ＋ 1）

答案出在leaf node : level = coins.length-1

                           100
level0 num of 25	  0 * 25	1*25	2*25 …..	   left_balance / 25
level1 num of 10    0	left_balance / 10 + 1
level2 num of 5     0 1 2
level3 num of 1     0 1 2 3 4 5 … 100
null                        |   |  |
public void dfs(int[] coins, int level, int left_balance, int[] sol, List<int[]> res){
    //base case(出答案的条件)
    if(level == coins.lenght-1){
        sol[level] = left_balabce;
        //add sol to res --> deep copy
      
        int[] newSol = new int[sol.length];
        for(int i = 0; i < sol.length; i++){
            newSol[i] = sol[i];
        }
        res.add(newSol); //or  res.add(sol.clone()); Arrays.copyof();
        return;
    }
    
    int num = left_balance / coins[level] + 1; //不取也是一种可能性
    for(int = 0; i < num; i++){
        sol[level] = i;
        dfs(coins, level + 1, left_balance - i *coins[level],sol, res)
        sol[level] = -1; // can be removed because assign, backtracing
    }
    
}

why deep copy: since we gonna do back tracing, 不然global地指向同一个array

L39 L40 L216 L 377 Combination Sum

Q4 L46 Permutations

Given a collection of distinct number, return all possible permutations

permutation size 不能变，一直向后看 向后swap

［1，2，3］ convert to string:

  • new String(array); "123"

  • String.valueOf(); "123"

  • Arrays.toString(); //反例"[1,2,3]"

private void dfs(char[] array, int index, List<String> result){
    //base case
    if(index == array.length - 1){
        result.add(new String(array));
        return;
    }
    for(int i = index; i < array.length; i++){
        //a
        swap(array, index, i);
        dfs(array,index + 1, result);
        swap(array, index, i); // backtracing? yes.
        //a
    }
    //return
}

why not i + 1: index是表示哪个位置该取谁，means level，不能产生变化

Previous数据结构相互实现（A.K.A）NextBit & Number & Math

Last updated

Was this helpful?