labuladong算法学习笔记

// 分解问题的解法
function maxDepth(root: TreeNode | null): number {
  if(root === null) return 0;
  let leftMax:number = maxDepth(root.left);
  let rightMax:number = maxDepth(root.right);
  let res = Math.max(leftMax, rightMax) + 1;
  return res;
};
// 遍历或者说回溯的解法
class Solution {
  res:number = 0;
  deep:number = 0;
  maxDepth(root: TreeNode | null):number{
    this.traverse(root);
    return this.res;
  }
  traverse(root: TreeNode | null):void {
    if(root === null) return;
    this.deep++;
    if(root.left === null && root.right === null) {
      this.res = Math.max(this.deep, this.res);
    }
    this.traverse(root.left);
    this.traverse(root.right);
    this.deep--;
  }
  static test(root){
    let demo = new Solution();
    let res = demo.maxDepth(root);
    return res;
  }
}

// 由于分解问题的方式代码看起来简洁
function preorderTraversal(root: TreeNode | null): number[] {
  if(!root || root.val===undefined) return [];
  let left:number[] = preorderTraversal(root.left);
  let right:number[] = preorderTraversal(root.right);
  return [].concat(root.val, left, right);
};
// 遍历的做法
class Solution {
  private res:number[] = [];

  preorderTraversal(root: TreeNode | null): number[]{
    this.traverse(root);
    return this.res;
  }

  traverse(root: TreeNode | null):void{
    if(!root || root.val ===undefined) return;
    this.res.push(root.val);
    this.traverse(root.left);
    this.traverse(root.right);
  }
  static test(root: TreeNode | null):number[]{
    let demo = new Solution();
    return demo.preorderTraversal(root);
  }
}

class Solution {
  private MaxPath = 0;
  diameterOfBinaryTree(root:TreeNode | null):number{
    this.deepMax(root);
    return this.MaxPath;
  }
  deepMax(root:TreeNode | null):number{
    if(!root || root.val === undefined) return 0;
    let leftMax = this.deepMax(root.left);
    let rightMax = this.deepMax(root.right);
    this.MaxPath = Math.max(this.MaxPath, leftMax + rightMax); // 在后续位置计算最大直径
    return 1 + Math.max(leftMax, rightMax); // 函数返回作为子树时的最大深度
  }
  static test(root: TreeNode | null): number {
    if(!root || root.val === undefined) return 0;
    let demo = new Solution();
    return demo.diameterOfBinaryTree(root);
  }
}

function invertTree(root: TreeNode | null): TreeNode | null {
  reverse(root);
  return root; // 遍历的方法
  // return recursion(root); // 递归方法
};

function reverse(root:TreeNode|null):TreeNode|null{
  if(!root) return null; // 交换左右节点，随后遍历其他节点
  let temp = root.left;
  root.left = root.right;
  root.right = temp;
  reverse(root.left);
  reverse(root.right);
}
function recursion(root:TreeNode|null):TreeNode|null{
  if(!root) return null; // 翻转左右子树
  let left = recursion(root.left);
  let right = recursion(root.right);
  root.left = right; // 交换左右子树
  root.right = left;
  return root;
}

function connect(root: Node | null): Node | null {
  if(root === null) return null;
  traverse(root.left, root.right); // 遍历“三叉树”，需要输入两个相邻的节点
  return root;
};

function traverse(node1:Node|null, node2:Node|null){
  if(node1 === null || node2 === null) return;
  node1.next = node2; // 连接两个相邻节点
  traverse(node1.left, node1.right); // 遍历下一个“三叉树”节点
  traverse(node2.left, node2.right);
  traverse(node1.right, node2.left);
}

function flatten(root: TreeNode | null): void {
  if(root === null) return;
  flatten(root.left); // 展开左右子树
  flatten(root.right);
  let left = root.left; // 缓存左右子树节点
  let right = root.right;
  root.left = null; // 连接root节点
  root.right = left;
  let p = root; // 循环遍历到拉伸后左子树的末尾节点
  while(p.right !== null){
    p = p.right;
  }
  p.right = right; // 连接右子树
};

function constructMaximumBinaryTree(nums: number[]): TreeNode | null {
  return build(nums, 0, nums.length - 1);
};
function build(nums:number[], start:number, end:number):TreeNode|null{
  if(start > end) return null;
  let maxVal = Number.MIN_SAFE_INTEGER;
  let index = -1;
  for(let i = start; i <= end; i++){ // 遍历查找最大值
    if(maxVal > nums[i]) continue;
    maxVal = nums[i];
    index = i;
  }
  let root = new TreeNode(maxVal); // 递归构造左右子树
  root.left = build(nums, start, index - 1);
  root.right = build(nums, index+1, end);
  return root;
}

function buildTree(preorder: number[], inorder: number[]): TreeNode | null {
  return build(preorder, inorder , [0, preorder.length - 1, 0, inorder.length - 1]);
};
function build(preorder:number[], inorder:number[], [pStart, pEnd, iStart, iEnd]:number[]){
  if(pStart > pEnd || iStart > iEnd) return null;
  let root = new TreeNode(preorder[pStart]); // 构造根节点
  let iRootIndex = -1; // 查找根节点在中序序列中的索引
  for(let i = iStart; i <= iEnd; i++){
    if(preorder[pStart] === inorder[i]) iRootIndex = i;
  }
  if(iRootIndex === -1) return null;
  let leftLength = iRootIndex - iStart; // 计算左子序列长度， PS：单闭区间长度
  root.left = build(preorder, inorder, [pStart+1, pStart+leftLength, iStart, iStart + leftLength - 1]); // 递归构造左右子树
  root.right = build(preorder, inorder, [pStart + leftLength + 1, pEnd, iRootIndex+1, iEnd]);
  return root;
}

function buildTree(inorder: number[], postorder: number[]): TreeNode | null {
  return build(inorder, postorder, [0, inorder.length-1, 0, postorder.length-1]);
};
function build(inorder:number[], postorder:number[], [iStart, iEnd, pStart, pEnd]:number[]):TreeNode |null {
  if(iStart > iEnd || pStart > pEnd) return null;
  let root = new TreeNode(postorder[pEnd]);
  let iRootIndex = -1;
  for(let i = iStart; i <= iEnd; i++){
    if(postorder[pEnd] === inorder[i]) iRootIndex = i;
  }
  if(iRootIndex === -1) return null;
  let leftLength = iRootIndex - iStart;
  root.left = build(inorder, postorder, [iStart, iRootIndex - 1, pStart, pStart + leftLength - 1]);
  root.right = build(inorder, postorder, [iRootIndex+1, iEnd, pStart + leftLength, pEnd - 1]);
  return root;
}

function constructFromPrePost(preorder: number[], postorder: number[]): TreeNode | null {
  return build(preorder, postorder, [0, preorder.length - 1, 0, postorder.length - 1]);
};

function build(preorder:number[], postorder:number[], [pStart, pEnd, bStart, bEnd]:number[]):TreeNode|null{
  if(pStart > pEnd || bStart > bEnd) return null;
  let root = new TreeNode(preorder[pStart]);
  if(pStart === pEnd) return root;
  let boundIndex = -1;
  for(let i = bStart; i < bEnd; i++){
    if(preorder[pStart+1] === postorder[i]) boundIndex = i;
  }
  if(boundIndex === -1) return null;
  let leftLength = boundIndex - bStart; // 半闭区间，但此时应包含root，故左区间终点+1
  root.left = build(preorder, postorder, [pStart+1, pStart+leftLength+1, bStart, boundIndex]); // 右子树起点对应调整
  root.right = build(preorder, postorder, [pStart+leftLength+2, pEnd, boundIndex+1, bEnd - 1]);
  return root;
}

function serialize(root: TreeNode | null): string {
  return Solution.layerSerialize(root);
};
function deserialize(data: string): TreeNode | null {
  let strArr = data.split(','); // 去掉分隔符，转换为数组方便处理
  return Solution.layerDeserialize(strArr);
};

class Solution {
  // 前序遍历实现
  static preSerialize(root:TreeNode|null):string{
    if(root === null) return '#';
    let res:string[] = []; // 先收集字符串，返回时使用分隔符拼接
    res.push(root.val.toString());
    res.push(Solution.preSerialize(root.left))
    res.push(Solution.preSerialize(root.right))
    return res.join(',');
  }
  static preDeserialize(strArr:string[]):TreeNode|null{
    if(strArr.length < 1) return null;
    let val = strArr.shift();
    if(val === '#') return null;
    let root = new TreeNode(Number(val));
    root.left = Solution.preDeserialize(strArr);
    root.right = Solution.preDeserialize(strArr);
    return root;
  }
  // 后序遍历实现
  static postSerialize(root:TreeNode|null):string{
    if(root === null) return '#';
    let res:string[] = [];
    res.push(Solution.postSerialize(root.left));
    res.push(Solution.postSerialize(root.right));
    res.push(root.val.toString());
    return res.join(',')
  }
  static postDeserialize(strArr:string[]):TreeNode|null{
    if(strArr.length < 1) return null;
    let val = strArr.pop();
    if(val === '#') return null;
    let root = new TreeNode(Number(val)); // 为了确定根节点，需要从右子树开始反序列化
    root.right = Solution.postDeserialize(strArr);
    root.left = Solution.postDeserialize(strArr);
    return root;
  }
  // 层序遍历实现
  static layerSerialize(root:TreeNode|null):string{
    let dp:Array<TreeNode|null> = [root]; // 队列存储节点
    let res:string[] = []; // 收集结果
    while(dp.length>0){
      let curNode = dp.shift();
      if(curNode === null){ // 遇到空节点收集结果，但不推入队列
        res.push('#');
        continue;
      };
      res.push(curNode.val.toString());
      dp.push(curNode.left, curNode.right); // 将左右子节点推入队列
    }
    return res.join(',');
  }
  static layerDeserialize(strArr:string[]):TreeNode|null{
    if(strArr.length < 1) return null;
    let val = strArr.shift();
    if(val === '#') return null;
    let root = new TreeNode(Number(val)); // 确定根节点
    let dp:TreeNode[] = [root]; // 使用队列存储节点
    while(dp.length > 0){
      let curNode = dp.shift();
      let leftVal = strArr.shift(); // 分别获取左右子节点的值进行判断
      let rightVal = strArr.shift();
      if(leftVal !== '#') { // 左子节点不为空则恢复节点并推入队列，若为空则不用处理
        curNode.left = new TreeNode(Number(leftVal));
        dp.push(curNode.left);
      }
      if(rightVal !== '#') {
        curNode.right = new TreeNode(Number(rightVal));
        dp.push(curNode.right);
      }
    }
    return root;
  }
}

function findDuplicateSubtrees(root: TreeNode | null): Array<TreeNode | null> {
  let soluton = new Solution();
  soluton.traverse(root);
  return soluton.res;
};
class Solution {
  cacheMap = new Map<string, number>();
  res:TreeNode[] = [];
  traverse(subRoot:TreeNode|null):string{
    if(subRoot === null) return '#';
    let res:string[] = [];
    res.push(this.traverse(subRoot.left));
    res.push(this.traverse(subRoot.right));
    res.push(subRoot.val.toString());
    let strTree = res.join(','); // 后序遍历序列化的过程会递归序列化子树，在此过程可查重
    if(this.cacheMap.get(strTree) === 1){ // 第二次出现，加入结果数组，增加次数
      this.res.push(subRoot);
      this.cacheMap.set(strTree, 2);
      // 首次出现，记录次数，出现次数>=2则不做记录，放置多次记录重复的子树
    } else if(!this.cacheMap.get(strTree)) this.cacheMap.set(strTree, 1);
    return strTree;
  }
}

function sortArray(nums: number[]): number[] {
  merge(nums, 0, nums.length - 1)
  return nums;
};
function merge(nums:number[], start, end):number[]{ // 选取闭区间[start, end]
  if(start >= end) return [] // 单个元素则直接返回
  let mid = start + Math.floor((end - start) / 2); // 确定分隔点
  merge(nums, start, mid); // 递归左右序列
  merge(nums, mid + 1, end); // 在后序遍历位置合并序列
  let left = start, right = mid + 1; // 双指针合并左右子数组(类似双指针合并链表)
  let res = new Array(end - start + 1).fill(-999);
  for(let i = 0; i <= end - start + 1; i++){
    if(left > mid){
      res.splice(i, end - right + 1, ...nums.slice(right, end+1))
      break;
    } else if (right > end){
      res.splice(i, mid - left + 1, ...nums.slice(left, mid+1))
      break;
    } else if (nums[left] > nums[right]){
      res[i] = nums[right];
      right++;
    } else if (nums[left] <= nums[right]){
      res[i] = nums[left];
      left++;
    }
  }
  nums.splice(start, end - start + 1, ...res);
  return nums;
}

function countSmaller(nums: number[]): number[] {
  let count = new Array(nums.length).fill(0);
  let tempArr = nums.map((val, index) => ({val, index})); // 辅助排序数组，记录到count的索引映射
  const mergeCount = (nums:{val:number, index:number}[], start, end) => {
    if(start >= end) return; // 对辅助数组进行归并排序
    let mid = start + Math.floor((end - start) / 2);
    mergeCount(nums, start, mid);
    mergeCount(nums, mid + 1, end);
    let left = start, right = mid + 1;
    let res = new Array(end - start + 1).fill(-999);
    for(let i = 0; i < end - start + 1; i++){
      if(left > mid){
        res[i] = nums[right++];
      } else if (right > end){ // 右侧序列全部填充，左侧剩余的元素都大于右侧序列
        res[i] = nums[left]; // 收集剩余的左侧元素，对每个左侧元素累计计数
        count[nums[left].index] += end - mid
        left++
      } else if (nums[left].val > nums[right].val){
        res[i] = nums[right++];
      } else if(nums[left].val <= nums[right].val){
        res[i] = nums[left]; // 收集左侧元素，统计此前已填充的右侧元素
        count[nums[left].index] += right - mid - 1
        left++
      }
    }
    nums.splice(start, end - start + 1, ...res);
  }
  mergeCount(tempArr, 0, tempArr.length - 1);
  return count;
};

function reversePairs(nums: number[]): number {
  let solution = new Solution();
  solution.merge(nums, 0, nums.length - 1);
  return solution.count;
};

class Solution {
  count:number = 0;
  merge(nums:number[], start:number, end:number){
    if(start >= end) return;
    let mid = start + Math.floor((end - start) / 2);
    this.merge(nums, start, mid);
    this.merge(nums, mid+1, end);
    let right = mid + 1;
    for(let left = start; left <= mid; left++){ // 对左序列的每个元素统计翻转对
      while(right <= end && nums[left]/2 > nums[right]) right++;
      this.count += right - (mid + 1); // 恰好不满足条件时，统计左闭右开区间元素数量
    } // 随后进行就地修改的归并排序
    let left = start, res = new Array(end - start + 1).fill(-999);
    right = mid + 1;
    for(let i = 0; i < end - start + 1; i++){
      if(left > mid){
        res.splice(i, end - right + 1, ...nums.slice(right, end + 1));
        break;
      } else if(right > end){
        res.splice(i, mid - left + 1, ...nums.slice(left, mid + 1));
        break;
      } else if(nums[left] > nums[right]){
        res[i] = nums[right++];
      } else if(nums[left] <= nums[right]){
        res[i] = nums[left++];
      }
    }
    nums.splice(start, end - start + 1, ...res);
    return nums;
  }
}

function countRangeSum(nums: number[], lower: number, upper: number): number {
  let demo = new Solution(nums, lower, upper);
  return demo.count;
};

class Solution {
  count:number = 0;
  preSum:number[] = [];
  lower:number;
  upper:number;
  constructor(nums:number[], lower:number, upper:number){
    this.lower = lower;
    this.upper = upper
    // 构造前缀和数组
    this.preSum = new Array(nums.length+1).fill(0);
    for(let i = 0; i < nums.length; i++){
      this.preSum[i+1] = nums[i] + this.preSum[i];
    }
    this.merge(this.preSum, 0, this.preSum.length - 1)

  }
  merge(nums:number[], start:number, end:number){
    if(start >= end) return;
    let mid = start + Math.floor((end - start)/2);
    this.merge(nums, start, mid);
    this.merge(nums, mid + 1, end);
    let minRight = mid + 1, maxRight = mid + 1; // 初始化最小/最大右边界
    for(let left = start; left <= mid; left++){ // 遍历左子序列作为左边界
      // 找到恰好满足条件的右边界(最小右边界)
      while(minRight <= end && nums[minRight] - nums[left] < this.lower) minRight++;
      // 找到恰好不满足的右边界(最大右边界)
      while(maxRight <= end && nums[maxRight] - nums[left] <= this.upper) maxRight++;
      this.count += maxRight - minRight; //统计满足条件的区间数量[minRight, maxRight）
    }
    let res = new Array(end - start + 1).fill(-999); // 归并排序
    let left = start, right = mid + 1;
    for(let i = 0; i < end - start + 1; i++){
      if(left > mid) {
        res.splice(i, end - right + 1, ...nums.slice(right, end + 1));
        break;
      } else if(right > end) {
        res.splice(i, mid - left + 1, ...nums.slice(left, mid + 1));
        break;
      } else if(nums[left] > nums[right]) res[i] = nums[right++];
      else if(nums[left] <= nums[right]) res[i] = nums[left++];
    }
    nums.splice(start, end - start +1, ...res);
  }
}

function kthSmallest(root: TreeNode | null, k: number): number {
  let solution = new Solution();
  solution.traverse(root, k);
  return solution.res;
};
class Solution {
  count:number = 0;
  res:number;
  traverse(root:TreeNode|null, k:number){
    if(root === null) return;
    this.traverse(root.left, k);
    this.count++; // 中序位置计数并判断是否为第k个
    if(this.count === k){
      this.res = root.val;
      return;
    }
    this.traverse(root.right, k);
  }
}

function convertBST(root: TreeNode | null): TreeNode | null {
  let solution = new Solution();
  solution.traverse(root);
  return root;
};
class Solution {
  sum:number = 0;
  traverse(root:TreeNode|null){
    if(root === null) return;
    this.traverse(root.right); // 先遍历右子树，即满足大于该节点的值先累加
    this.sum += root.val; // 中序位置累加，并更新节点值
    root.val = this.sum;
    this.traverse(root.left);
  }
}

function isValidBST(root: TreeNode | null): boolean {
  return Solution.isValidBST(root, null, null); // 初始判断将任务交由边界重叠的左右递归
};

class Solution {
  static isValidBST(root: TreeNode, min:TreeNode, max:TreeNode){
    if(root === null) return true;
    // 判断大小与递归条件判断有部分重叠，这样才能保证能进行连续递归
    if(min != null && root.val <= min.val) return false;
    if(max != null && root.val >= max.val) return false;
    // 左子树的最大值即为root.val， 右子树的最小值为root.val
    return Solution.isValidBST(root.left, min, root) && Solution.isValidBST(root.right, root, max);
  }
}

function searchBST(root: TreeNode | null, val: number): TreeNode | null {
  if(root === null) return null;
  if(root.val > val) return searchBST(root.left, val);
  if(root.val < val) return searchBST(root.right, val);
  return root;
};

function insertIntoBST(root: TreeNode | null, val: number): TreeNode | null {
  if(root === null) return new TreeNode(val);
  if(root.val > val){ // 为了链接创建的node，需要接收递归函数的返回节点
    root.left = insertIntoBST(root.left, val);
  } else if(root.val < val){
    root.right = insertIntoBST(root.right, val);
  }
  return root;
};

function deleteNode(root: TreeNode | null, key: number): TreeNode | null {
  if(root === null) return null;
  // 先找到要刪除节点的位置
  if(root.val === key){
    // 若该节点为叶子结点，则直接删除，返回null即可
    if(root.left === null && root.right === null) return null;
    // 若该节点仅有一个子节点，则返回对应子节点即相当于删除当前节点
    if(root.left === null) return root.right;
    if(root.right === null) return root.left;
    // 若该节点有左右子节点，则需要找到左子树中最大值或右子树中的最小值来替换当前节点
    let min:TreeNode = getMin(root.right); // 以右子树中的最小值为例
    root.right = deleteNode(root.right, min.val); // 从右子树中删除找到的最小值
    // 将最小值替换为当前节点，即相当于删除了当前节点
    min.left = root.left;
    min.right = root.right;
    root = min;
  } else if(root.val > key){
    root.left = deleteNode(root.left, key);
  } else if(root.val < key){
    root.right = deleteNode(root.right, key);
  }
  return root;
};
function getMin(node:TreeNode):TreeNode{ // 循环查找右子树中的最小值
  while(node.left !== null) node = node.left;
  return node;
}

function numTrees(n: number): number {
  let demo = new Solution(n);
  return demo.count(1, n);
};

class Solution {
  cache:number[][]; // 缓存已经计算过的组合，加速计算过程
  constructor(n:number){
    this.cache = new Array(n+1).fill(0).map(i => new Array(n+1).fill(0));
  }
  count(left:number, right:number):number{
    if(left > right) return 1; // 空区间节点为null ，组合数为1
    let res = 0; // 初始化本区间组合数，查表有值则直接返回
    if(this.cache[left][right] != 0) return this.cache[left][right];
    for(let i = left; i <= right; i++){ // 循环固定区间中的i节点
      let nLeft = this.count(left, i - 1); // 每轮循环中计算左右子树的组合数
      let nRight = this.count(i+1, right);
      res += nLeft * nRight; // 左右子树相乘即为本轮循环的组合数，累计记录
    }
    this.cache[left][right] = res; // 将对应区间的组合数存入表中，并返回对应的值
    return res;
  }
}

function generateTrees(n: number): Array<TreeNode | null> {
  if(n === 0) return [];
  return build(1, n);
};

function build(left:number, right:number):Array<TreeNode|null>{
  let res:Array<TreeNode|null> = []
  if(left > right){
    res.push(null);
    return res;
  }

  for(let i = left; i <= right; i++){
    let NLeft = build(left, i - 1);
    let NRight = build(i+1, right);

    for( let NL of NLeft){
      for(let NR of NRight){
        let root = new TreeNode(i);
        root.left = NL;
        root.right = NR;
        res.push(root);
      }
    }
  }
  return res;
}

function sortArray(nums: number[]): number[] {
  if(nums.length <= 1) return nums;
  quickSort(nums, 0, nums.length - 1);
  return nums;
};

function quickSort(nums:number[], left:number, right:number):void{
  if(left >= right) return;
  let p = partition(nums, left, right);
  quickSort(nums, left, p-1);
  quickSort(nums, p+1, right);
}

function partition(nums:number[], left:number, right:number):number{
  let mid = nums[left];
  let i = left + 1, j = right;
  while(i <= j){
    while(i < right && nums[i] <= mid) i++;
    while(j > left && nums[j] > mid) j--;
    if(i >= j) break;
    let temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
  }
  let temp = nums[left];
  nums[left] = nums[j];
  nums[j] = temp;
  return j;
}

function findKthLargest(nums: number[], k: number): number {
  let i = 0, j = nums.length - 1;
  k = nums.length - k;
  while(i <= j){
    let p = partition(nums, i, j);
    if(p < k) i = p+1;
    else if(p > k) j = p - 1;
    else return nums[p]
  }
  return -1
};

function partition(nums:number[], left:number, right:number):number{
  if(left >= right) return right;
  let mid = nums[left];
  let i = left + 1, j = right;
  while(i <= j){
    while(i < right && nums[i] <= mid) i++;
    while(j > left && nums[j] > mid) j--;
    if(i >= j) break;
    let temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
  }
  let temp = nums[j];
  nums[j] = nums[left];
  nums[left] = temp;
  return j;
}

function lowestCommonAncestor(root: TreeNode | null, p: TreeNode | null, q: TreeNode | null): TreeNode | null {
  if(!root) return null;
  if(root.val === p.val || root.val === q.val) return root; // 为当前节点
  let left = lowestCommonAncestor(root.left, p, q); // 遍历左子树查找
  let right = lowestCommonAncestor(root.right, p, q);
  if(left !== null && right !== null) return root; // 收集左右子树节点并判断
  return left !== null ? left : right; // 返回不为空的节点，若都为空则返回空节点
};

let foundP = false, foundQ = false;

function lowestCommonAncestor(root: TreeNode | null, p:TreeNode|null, q:TreeNode|null): TreeNode | null {
  let res = find(root, p.val, q.val);
  if(!foundP || !foundQ) return null;
  return res;
};

function find(root:TreeNode|null, val1:number, val2:number):TreeNode|null{
  if(root === null) return null;
  let left = find(root.left, val1, val2);
  let right = find(root.right, val1, val2);
  if(left !== null && right !== null) return root;
  if(root.val === val1 || root.val === val2){
    if(root.val === val1) foundP = true;
    if(root.val === val2) foundQ = true;
    return root;
  }
  return left !== null ? left : right;
}

function lowestCommonAncestor(root: TreeNode | null, nodes:TreeNode[]): TreeNode | null {
  let valueHash = new Set();
  nodes.forEach(i => {
    valueHash.add(i.val);
  })
  return find(root, valueHash);
};

function find(root:TreeNode|null, values:Set<typeof root.val>):TreeNode|null{
  if(!root) return null;
  if(values.has(root.val)) return root;
  let left = find(root.left, values);
  let right = find(root.right, values);
  if(left !== null && right !== null) return root;
  return left !== null ? left : right;
}

function lowestCommonAncestor(root: TreeNode | null, p:TreeNode|null, q:TreeNode|null): TreeNode | null {
  let val1 = Math.min(p.val, q.val);
  let val2 = Math.max(p.val, q.val);
  return find(root, val1, val2);
};

function find(root:TreeNode|null, val1:number, val2:number):TreeNode|null{
  if(root === null) return null;
  if(root.val > val2) return find(root.left, val1, val2); // 节点过大，在左子树中找
  if(root.val < val1) return find(root.right, val1, val2);
  return root;
}

class NestedIterator {
  list: Array<NestedInteger>
  constructor(nestedList: NestedInteger[]) {
    this.list = nestedList;
  }

  hasNext(): boolean { // 在hasNext中迭代保证this.list第一个元素为整数
    while (this.list.length > 0 && !this.list[0].isInteger()) {
      let temp = this.list.shift().getList();
      for (let i = temp.length - 1; i >= 0; i--) { // 倒序遍历，保持节点拍平顺序
        this.list.unshift(temp[i]);
      }
    }
    return this.list.length > 0;
  }

  next(): number {
    return this.list.shift().getInteger();
  }
}

function countNodes(root: TreeNode | null): number {
  let left = root, right = root;
  let hLeft = 0, hRight = 0; // 沿着左侧和右侧分别计算高度
  while(left != null){
    left = left.left;
    hLeft++;
  }
  while(right != null){
    right = right.right;
    hRight++;
  } // 若高度相同则使用满二叉树的计算方法，否则使用普通二叉树的递归统计方法
  if(hLeft === hRight) return Math.pow(2, hLeft) - 1;
  return 1 + countNodes(root.left) + countNodes(root.right);
};

function coinChange(coins: number[], amount: number): number {
  // 初始化dp为amount+1，就因为凑成amount最多使用amount个硬币
  let dp:number[] = new Array(amount+1).fill(amount+1);
  dp[0] = 0; // 初始话起始值
  for(let i = 0; i < dp.length; i++){ // 循环计算每个金额所需要的最少硬币数
    for(let coin of coins){ // 遍历尝试每个硬币组合
      if(i - coin < 0) continue; // 若遇到无法达成的组合则直接跳过
      dp[i] = Math.min(dp[i], 1 + dp[i - coin]); // 比较与更新硬币组合数
    }
  }
  // 若目标金额仍等于初始值，则返回无法凑成的结果
  return (dp[amount] === amount + 1) ? -1 : dp[amount]; 
};

function fib(n: number): number {
  let dp:[number, number] = [1, 1];
  if(n <= 0) return 0;
  if(n === 1 || n === 2) return dp[0];
  for(let i = 3; i <= n; i++) {
    let tmp = dp[0] + dp[1];
    dp[0] = dp[1];
    dp[1] = tmp;
  }
  return dp[1];
};

interface Visited {[key:number]: boolean};

function permute(nums: number[]): number[][] {
  if(nums.length === 0) return [[]];
  if(nums.length === 1) return [nums];
  let demo = new Solution();
  return demo.permute(nums);
};

class Solution {
  res:number[][] = [];
  permute(nums: number[]): number[][] {
    // 主函数中初始化visited记录访问过的数字，track记录访问路径，即排列
    let visited:Visited = {};
    let track:number[] = [];
    this.backtrack(nums, track, visited);
    return this.res;
  }
  backtrack(nums:number[], track:number[], visited:Visited){
    if(track.length === nums.length){ // 终止条件，存储一种排列并返回
      this.res.push([...track]);
      return
    }
    for(let i = 0; i < nums.length; i++) {
      const val = nums[i];
      if(visited[val]) continue; // 跳过已访问的数字
      visited[val] = true; // 递归前标记访问，并记录节点
      track.push(val)
      this.backtrack(nums, track, visited);
      visited[val] = false; // 递归返回后，删除标记，并删除节点
      track.pop();
    }
  }
}

function solveNQueens(n: number): string[][] {
  let demo = new Solution();
  return demo.solveNQueens(n);
};

class Solution {
  res:string[][] = [];
  solveNQueens(n: number): string[][] {
    let solve:string[][] = new Array(n).fill(0).map(item => new Array(n).fill('.'))
    solve[0][0] = 'Q';
    this.backtrack(solve, 0)
    return this.res;
  }
  backtrack(track:string[][], row:number){
    if(row === track.length){ // 本轮递归超过最后一行，因此收集结果结束递归
      this.res.push(track.map(item => item.join('')));
      return;
    }
    for(let col = 0; col < track.length; col++){ // 遍历当前列
      if(!this.isValid(col, row, track)) continue;
      track[row][col] = 'Q'; // 递归前标记
      this.backtrack(track, row+1); // 递归新的行
      track[row][col] = '.'; // 递归后回溯
    }

  }
  isValid(col:number, row:number, track:string[][]):boolean {
    let n = track.length; // 判断该位置是否能放置一个皇后
    for(let i = 0; i < row; i++){
      if(track[i][col] === 'Q') return false;
    }
    for(let i = row - 1, j = col - 1; i >=0 && j >= 0; i--, j--){
      if(track[i][j] === 'Q') return false;
    }
    for(let i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++){
      if(track[i][j] === 'Q') return false
    }
     return true;
  }
}

function minDepth(root: TreeNode | null): number {
  if(root == null) return 0;
  let queue:TreeNode[] = [];
  queue.push(root);
  let deep = 1; // 初始化层数
  while(queue.length > 0){
    let length = queue.length;
    for(let i = 0; i < length; i++) { // 仅对长度进行循环，不使用索引
      let cur:TreeNode = queue.shift(); // 每次从队头推出一个节点
      if(cur.left === null && cur.right === null) return deep; // 找到叶子节点则直接返回
      if(cur.left !== null) queue.push(cur.left); // 依次推入左右节点
      if(cur.right !== null) queue.push(cur.right);
    }
    deep++; // 遍历完一层更新层数
  }
  return deep;
};

function openLock(deadends: string[], target: string): number {
  let visited:Set<string> = new Set(); // 使用set记录访问记录，在visited中的组合不会被分析
  for(let key of deadends) visited.add(key); // 将deadends加入到visited中便于跳过
  let queue:string[] = ['0000']; // 初始化队列
  let step = 0;
  while(queue.length > 0) { // 队列不为空时进行遍历
    let len = queue.length;
    for(let i = 0; i < len; i++) { // 取当前层剩余的节点数作为遍历次数，而不用做索引
      let cur = queue.shift(); // 从队头中推出当前组合(节点)
      if(visited.has(cur)) continue // 当前节点已访问过或在deadends中则跳过该组合分析
      else visited.add(cur); // 将当前节点加入到visited中，避免后续重复分析
      if(cur == target) return step; // 若当前节点刚好等于目标密码，则直接返回步数
      for(let j = 0; j < 4; j++){ // 收集该组合(节点)的下一步可能状态，8种
        let tmp = plusOne(cur, j); // j position add number
        if(!visited.has(tmp)){ // node  visited then add to queue
          queue.push(tmp);
        }
        tmp = minusOne(cur, j); // j position minus number
        if(!visited.has(tmp)){
          queue.push(tmp);
        }
      }
    }
    step++; // analyze one node then add step
  }
  return -1; // not found solution then return -1
};
// circular add one
function plusOne(s:string, j:number):string{
  let tmp = Array.from(s);
  if(tmp[j] == '9') tmp[j] = '0'
  else tmp[j] = String(Number(tmp[j]) + 1)
  return tmp.join('');
}
// circular minus one
function minusOne(s:string, j:number):string{
  let tmp = Array.from(s);
  if(tmp[j] == '0') tmp[j] = '9'
  else tmp[j] = String(Number(tmp[j]) - 1);
  return tmp.join('');
}