【当前无排名】挑战leetcode进入前1w名

李恒道

https://leetcode.cn/problems/binary-tree-right-side-view/submissions/561308653/?envType=study-plan-v2&envId=top-100-liked
缝缝补补又凹一题

var rightSideView = function (root) {
  const ret = [];
  if(root==null){
    return []
  }
  let stack = [root];
  do {
    const nextStack = [];
    for (let index = 0; index < stack.length; index++) {
      const node = stack[index];
      if (node == null) {
        continue;
      }
      if(node.left){
        nextStack.push(node.left)
      }
      if(node.right){
        nextStack.push(node.right)
      }
    }
    if (stack.length != 0) {
      ret.push(stack[stack.length - 1].val);
    }
    stack = nextStack;
  } while (stack.length != 0);
  return ret;
};

李恒道

这题没反应过来就过了...
https://leetcode.cn/problems/flatten-binary-tree-to-linked-list/submissions/561311668/?envType=study-plan-v2&envId=top-100-liked

var flatten = function (root) {
  if (root == null) {
    return null;
  }
  const handleFlatten = (root) => {
    let leftPtr = undefined;
    if (root.left) {
      leftPtr = handleFlatten(root.left) ?? root.left;
    }
    let rightPtr = undefined;
    if (root.right) {
      rightPtr = handleFlatten(root.right) ?? root.right;
    }
    if (leftPtr) {
      leftPtr.left = null;
      leftPtr.right = root.right;
    }
    const left = root.left;
    const right = root.right;
    root.left = null;
    root.right = left ?? right;

    return rightPtr ?? leftPtr;
  };
  handleFlatten(root);
  return root;
};

李恒道

边界大法秒！
https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/submissions/561312292/?envType=study-plan-v2&envId=top-100-liked

var buildTree = function (preorder, inorder) {
  const buildNode = (pl, pr, il, ir) => {
    if (pl == pr) {
      return {
        left: null,
        right: null,
        val: preorder[pl],
      };
    }
    if(pl>pr){
      return null
    }
    const node = {
      left: null,
      right: null,
      val: preorder[pl],
    };
    const centerIndex = inorder.findIndex((element) => element == node.val);
    const newPL = pl + (centerIndex - il);
    node.left = buildNode(pl + 1, newPL, il, centerIndex - 1);
    node.right = buildNode(newPL + 1, pr, centerIndex + 1, ir);
    return node;
  };
  return buildNode(0, preorder.length - 1, 0, inorder.length - 1);
};

李恒道

打个简单题换换心情
https://leetcode.cn/problems/single-number/?envType=study-plan-v2&envId=top-100-liked

var singleNumber = function(nums) {
  let ret=0
  for (let index = 0; index < nums.length; index++) {
    ret=ret^nums[index];

  }
  return ret
};

李恒道

岛屿题，下沉法，秒
https://leetcode.cn/problems/number-of-islands/submissions/561313020/?envType=study-plan-v2&envId=top-100-liked

var numIslands = function (grid) {
  let ret = 0;
  const clearIsland = (x, y) => {
    if (x < 0 || x >= grid.length) {
      return;
    }
    if (y < 0 || y >= grid[0].length) {
      return;
    }
    if (grid[x][y] == 1) {
      grid[x][y] = 0;
      clearIsland(x - 1, y);
      clearIsland(x + 1, y);
      clearIsland(x, y + 1);
      clearIsland(x, y - 1);
    }
  };
  for (let index = 0; index < grid.length; index++) {
    const col = grid[index];
    for (let indey = 0; indey < col.length; indey++) {
      const item = col[indey];
      if (item == 1) {
        ret++;
        clearIsland(index, indey);
      }
    }
  }
  return ret;
};

李恒道

hash+递归直接秒
https://leetcode.cn/problems/path-sum-iii/submissions/561336523/?envType=study-plan-v2&envId=top-100-liked

var pathSum = function (root, targetSum) {
  const map = new Map();
  map.set(0,1)
  let ret = 0;
  let presum = 0;
  const dfs = (root) => {
    if(root==null){
      return
    }
    const haveNum =presum- (targetSum - root.val);
    if (map.has(haveNum)) {
      ret += map.get(haveNum);
    }
    presum += root.val;
    if (map.has(presum)) {
      map.set(presum, map.get(presum) + 1);
    } else {
      map.set(presum, 1);
    }
    dfs(root.left);
    dfs(root.right);
    map.set(presum, map.get(presum) - 1);
    presum -= root.val;
  };
  dfs(root);
  return ret;
};

李恒道

嫖到的一个二叉树建立的辅助函数

class TreeNode {
  constructor(val) {
      this.val = val;
      this.left = null;
      this.right = null;
  }
}

function buildTree(arr) {
  if (!arr.length) return null;

  let root = new TreeNode(arr[0]);
  let queue = [root];
  let i = 1;

  while (i < arr.length) {
      let current = queue.shift();

      if (arr[i] !== null) {
          current.left = new TreeNode(arr[i]);
          queue.push(current.left);
      }
      i++;

      if (i < arr.length && arr[i] !== null) {
          current.right = new TreeNode(arr[i]);
          queue.push(current.right);
      }
      i++;
  }

  return root;
}

李恒道

橘子问题，利用数组秒

/**
 * @param {number[][]} grid
 * @Return {number}
 */
var orangesRotting = function (grid) {
  let decayArr = [];
  let total = 0;
  for (let index = 0; index < grid.length; index++) {
    for (let indey = 0; indey < grid[0].length; indey++) {
      if (grid[index][indey] == 2) {
        decayArr.push({ index, indey });
        total++;
      }
      if (grid[index][indey] == 1) {
        total++;
      }
    }
  }
  let minues = -1;
  let noFind = true;
  const decay = (x, y) => {
    const position = [
      [x - 1, y],
      [x + 1, y],
      [x, y + 1],
      [x, y - 1],
    ];
    for (let index = 0; index < position.length; index++) {
      const pos = position[index];
      const x = pos[0];
      const y = pos[1];
      if (x < 0 || x >= grid.length) {
        continue;
      }
      if (y < 0 || y >= grid[0].length) {
        continue;
      }

      if (grid[pos[0]][pos[1]] == 1) {
        grid[pos[0]][pos[1]] = 2;
        decayArr.push({
          index: x,
          indey: y,
        });
        noFind = false;
      }
    }
  };
  do {
    minues++;
    noFind = true;
    const cycle = [...decayArr];
    for (let index = 0; index < cycle.length; index++) {
      const orange = decayArr[index];
      decay(orange.index, orange.indey);
    }
  } while (noFind == false);
  return total==decayArr.length? minues:-1;
};

李恒道

https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/submissions/562017729/?envType=study-plan-v2&envId=top-100-liked
边界没扣明白，看了一下答案

var lowestCommonAncestor = function (root, p, q) {
    let result = undefined
    const dfs = (root) => {
        if(root==null){
            return false
        }
        const left = dfs(root.left);
        const right = dfs(root.right);
        if (left && right) {
            result = result ?? root
        }
        if ((left || right) && ((root == p) || (root == q))) {
            result = result ?? root
        }
        return left || right || (root == p) || (root == q)
    }
    dfs(root)
    return result
};

李恒道

https://leetcode.cn/problems/binary-tree-maximum-path-sum/submissions/562017878/?envType=study-plan-v2&envId=top-100-liked
递归题，扫了一眼答案

var maxPathSum = function (root) {
    let max = Number.MIN_SAFE_INTEGER
    const dfs = (node) => {
        if (node == null) {
            return 0
        }
        let left = Math.max(dfs(node.left), 0)
        let right = Math.max(dfs(node.right), 0)
        max=Math.max(max,left+right+node.val)
        return Math.max(Math.max(left, right) + node.val, 0)

    }
    dfs(root)
    return max
};