[JS] - [DFS, BFS application] - learning notes

1 Traversal of binary tree - recursive -DFS

//  The input parameters of all traversal functions are the root node objects of the tree 
function preorder(root) {
    
    //  Recursive boundary ,root  It's empty 
    if(!root) {
    
        return 
    }
     
    //  Output the current traversal node value 
    console.log(' The node value currently traversed is ：', root.val)  
    //  Recursively traverses the left subtree  
    preorder(root.left)  
    //  Recursively traverses the right subtree  
    preorder(root.right)
}

2 Sequence traversal of binary tree -BFS

function BFS(root) {
    
    const queue = [] //  Initialize queue queue
    //  The root node joins the team first 
    queue.push(root)
    //  The queue is not empty , Description not completely traversed 
    while(queue.length) {
    
        const top = queue[0] //  Take out the team leader element  
        //  visit  top
        console.log(top.val)
        //  If the left subtree exists , Zuozhu joins the team 
        if(top.left) {
    
            queue.push(top.left)
        }
        //  If the right subtree exists , Right subtree joins the team 
        if(top.right) {
    
            queue.push(top.right)
        }
        queue.shift() //  Access to complete , Team leader element out of the team 
    }
}
BFS(root) // perform BFS

3 Given a sequence without repeating numbers , Return all possible permutations

https://mp.csdn.net/mp_blog/creation/success/124684440

 Example ：   
 Input : [1,2,3]
 Output : [
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]

//  The input parameter is an array 
const permute = function(nums) {
    
  //  The length of the cache array 
  const len = nums.length
  // curr  Variable is used to record the current arrangement 
  const curr = []
  // res  Used to record all the permutations 
  const res = []
  // visited  To avoid repeating the same number 
  const visited = {
    }
  //  Definition  dfs  function , The input parameter is the index of the pit （ from  0  Count ）
  function dfs(nth) {
    
  
      #  If you traverse to a nonexistent pit （ The first  len+1  individual ）, Touch the recursive boundary to return 
      if(nth === len) {
    
          //  Before this time  len  Pits have been filled , Record the corresponding arrangement 
          res.push(curr.slice())
          return 
      }
      //  Check what numbers are left in your hand 
      for(let i=0;i<len;i++) {
    
          //  if  nums[i]  It has not been used by other pits before , It can be understood as “ This number is left ”
          if(!visited[nums[i]]) {
    
              #  to  nums[i]  To make a “ Used ” Mark of 
              visited[nums[i]] = 1
              //  take nums[i] Push current arrangement 
              curr.push(nums[i])
              //  Based on this arrangement, continue to the next pit 
              dfs(nth+1) 
              // nums[i] Get out of the current pit 
              curr.pop()
              //  Fall down “ Used ” identification 
              visited[nums[i]] = 0
          }
      }
  }
  #  From index to  0  Pit position （ That is, the first pit ） Start  dfs
  dfs(0)
  return res
};

res.push(curr.slice()) Not simply res.push(curr) . Why do you do this ？ Because there is only one unique curr , curr The value of dfs And constantly updated . slice The function of the method is to help us copy out one that does not affect curr A copy of the original , In case of direct modification to curr References to .

4 Given a set of integers without repeating elements nums, Returns all possible subsets of the array

https://mp.csdn.net/mp_blog/creation/success/124684440

 Example :  Input : nums = [1,2,3]
 Output :
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]

const combine = function(n, k) {
    
   //  Initializing the result array 
    const res = []   
    //  Initialize the combined array 
    const subset = []
    //  Get into  dfs, The starting number is 1
    dfs(1)  

    //  Definition  dfs  function , The input parameter is the number currently traversed 
    function dfs(index) {
    
        if(subset.length === k) {
    
            res.push(subset.slice())
            return 
        }
        //  Start with the value of the current number , Traverse  index-n  All numbers between 
        for(let i=index;i<=n;i++) {
    
            //  This is the case when the current number exists in the combination 
            subset.push(i) 
            //  Based on the fact that the current number exists in the combination , further  dfs
            dfs(i+1)
            //  This is the case when the current number does not exist and is being combined 
            subset.pop()
        }
    }
    //  Return result array 
    return res 
};

function allSubsets(arr){
    
	let res = [[]];
	for(let i = 0; i < arr.length; i++){
    
		const tempRes = res.map(subset => {
    
			const one = subset.concat([]);
			one.push(arr[i]);
			return one;
		})
		res = res.concat(tempRes);
	}
	return res;
}