全排列

image-20210504092842700.png

  1. /**
  2.  * @param {number[]} nums
  3.  * @return {number[][]}
  4.  */
  5.  Array.prototype.contains = function(num){
  6.     for(let i=0;i<this.length;i++){
  7.         if(this[i]===num){
  8.             return true;
  9.         }
  10.     }
  11.     return false;
  12. };
  13. var permute = function(nums) {
  14.     let res = [];
  15.     let track = [];
  16.     backtrack(nums,track);
  17.     return res;
  19.     function backtrack(nums,track){
  20.         if(nums.length===track.length){
  21.             let newTrack = [];
  22.             Object.assign(newTrack,track)
  23.             res.push(newTrack);
  24.             return;
  25.         }
  26.         for(let num of nums){
  27.             if(track.contains(num)){
  28.                 continue;
  29.             }
  30.             track.push(num);
  31.             backtrack(nums,track);
  32.             track.pop();
  33.         }
  34.     }
  35. };

子集

image-20210504093621622.png
这个需要剪枝：
dfs2.png

  1. /**
  2.  * @param {number[]} nums
  3.  * @return {number[][]}
  4.  */
  5. var subsets = function(nums) {
  6.     let res = [];
  7.     let track = [];
  8.     trackback(nums,track,0);
  9.     return res;
  11.     function trackback(nums,track,start){
  12.         let newTrack = [];
  13.         Object.assign(newTrack,track);
  14.         res.push(newTrack);
  15.         for(let i=start;i<nums.length;i++){
  16.             track.push(nums[i]);
  17.             trackback(nums,track,i+1)
  18.             track.pop();
  19.         }
  20.     }
  21. };

二叉树最小高度

image-20210504094011605.png

  1. 输入：root = [3,9,20,null,null,15,7]
  2. 输出：2
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var minDepth = function (root) {
    if (!root === true) {
        return 0;
    }
    let queue = [];
    let depth = 1;
    queue.push(root);
    while (queue.length !== 0) {
        // 踩坑：这里queue.length要另外写在外面，要是写在循环里是动态改变的，最终结果始终输出1
        let ql = queue.length;
        for (let i = 0; i < ql; i++) {
            let cur = queue.shift();
            if (cur.left === null && cur.right === null) {
                return depth;
            }
            if (cur.left !== null) {
                queue.push(cur.left);
            }
            if (cur.right !== null) {
                queue.push(cur.right);
            }
        }
        depth++;
    }
    return depth;
};