基于typescript实现剑指offer中的算法

// 利用闭包或静态变量等方式存储instance，分离构造器和单例判断函数
class singleton {
  private static instance:singleton;
  public name:string;
  constructor(name:string) {
    this.name = name;
  }

  /**
   * @description: 单例判断函数，通过此函数获取单例
   * @param {*}
   * @return {*}
   */
  static getSingleton(name:string):singleton {
    return this.instance || (this.instance = new singleton(name));
  }

  /**
   * @description: 测试用例
   * @param {*}
   * @return {*}
   */
  static test() {
    let obj1 = new singleton('obj1');
    let obj2 = singleton.getSingleton('obj2');
    let obj3 = singleton.getSingleton('obj3');
    console.log(obj1 === obj2);
    console.log(obj2 === obj3);
  }
}
singleton.test(); // 运行测试用例

class Demo {
  static duplicate(arr:number[]):number{
    let length = arr.length;
    if(length < 2) return -1;
    for(let i = 0; i < length; i++){
      // 不满足限定范围则直接返回
      if(arr[i] < 0 || arr[i] > length -1) return -1;
      // 当arr[i] !== arr[arr[i]]时，需交换值，交换后arr[i]位置满足该条件，但i位置不一定满足该条件，因此需要加入内层循环，此举并不会增加时间复杂度，因为后续的位置以基本满足该条件不会继续循环
      while(arr[i] !== i){
        if(arr[i] !== arr[arr[i]]){
          let temp = arr[arr[i]];
          arr[arr[i]] = arr[i];
          arr[i] = temp;
        }else{
          return arr[i]
        }
      }
    }
    return -1
  }
  static test() {
    let testArr = [2,3,1,0,2,5,3];
    console.log(Demo.duplicate(testArr))
  }
}

Demo.test();

class Demo {
  static findInArr(arr:number[][], target:number):boolean{
    if(arr.length <= 0 || arr[0].length <= 0) return false;
    let i = 0, j = arr[0].length - 1;
    while(i < arr.length && j > 0){
      if(arr[i][j] > target){
        j--;
      }else if(arr[i][j] < target){
        i++;
      }else return true;
    }
    return false
  }
  static test() {
    let testArr = [
      [1,2,8,9],
      [2,4,9,12],
      [4,7,10,13],
      [6,8,11,15]
    ];
    console.log(Demo.findInArr(testArr, 3))
  }
}
Demo.test();

class Demo {
  static replaceSpace(s:string):string {
    let data = Array.from(s);
    let length = data.length;
    let count = 0;
    for(let i = 0; i < length; i++){
      if(data[i] === ' ') count++;
    }
    data = data.concat(new Array(count*2).fill(''));
    let tail = data.length - 1, target = length -1;
    while(tail !== target){
      if(data[target] === ' '){
        data[tail--] = '0';
        data[tail--] = '2';
        data[tail--] = '%';
        target--;
      }else{
        data[tail--] = data[target--];
      }
    }
    return data.join('');
  }
  static test() {
    let testArr = 'We Are Happy.'
    console.log(Demo.replaceSpace(testArr))
  }
}
Demo.test();

interface ListNode<T> {
  value:T,
  next:ListNode<T>|undefined
}
class NumberNode implements ListNode<number> {
  value:number;
  next:ListNode<number>|undefined;
  constructor(val:number, next:NumberNode|undefined = undefined){
    this.value = val;
    this.next;
  }
}
class Demo {
  static reverse<T>(head:ListNode<T>):void{
    let res:T[] = [];
    let p = head;
    while(p){
      res.push(p.value);
      p = p.next;
    }
    for(let i = res.length - 1; i >= 0; i--){
      console.log(res[i]);
    }
  }
  static test() {
    let testArr = [1,2,3,4,5]
    const head = new NumberNode(testArr[0]);
    let p = head;
    for(let i = 1; i < testArr.length; i++){
      p.next = new NumberNode(testArr[i]);
      p = p.next;
    }
    Demo.reverse(head);
  }
}
Demo.test();

class TreeNode<T> {
  val:T
  left:TreeNode<T>|undefined;
  right:TreeNode<T>|undefined;
  constructor(val:T, left:TreeNode<T>|undefined = undefined, right:TreeNode<T>|undefined = undefined){
    this.val = val;
    this.left = left;
    this.right = right;
  }
  static preRoot<T>(root:TreeNode<T>){ // 定义前序遍历算法，用于测试用例校验
    if(root) console.log(root.val);
    if(root?.left) TreeNode.preRoot(root.left);
    if(root?.right) TreeNode.preRoot(root.right);
  }
}
class Demo {
  static rebuildTree<T>(pre:T[], vin:T[], indexArr?:number[]):TreeNode<T>|undefined{
    // 若未传入索引数组，则进行初始化
    if(!indexArr) indexArr = [0, pre.length, 0, vin.length];
    // 若前序和中序长度不相等，则抛出错误
    if(indexArr[1] - indexArr[0] !== indexArr[3] - indexArr[2]) throw new Error('pre.length must eq vin.length');
    // 若长度同为0 则直接返回undefined
    if(indexArr[1] - indexArr[0] === 0 || indexArr[3] - indexArr[2] === 0) return undefined;
    // 经过前面的条件判断，确定前序和中序长度相等，且至少有一个节点，因此初始化根节点
    let root = new TreeNode(pre[indexArr[0]]);
    // 若长度为1则直接返回该根节点
    if(indexArr[1] - indexArr[0] === 1 && indexArr[3] - indexArr[2] === 1) return root;
    // 计算根节点在中序中的索引位置，然后计算左子树和右子树的长度
    let vinRoot = vin.indexOf(pre[indexArr[0]]);
    let leftLen = vinRoot - indexArr[2];
    let rightLen = indexArr[3] - vinRoot - 1; // vinRoot + 1 才是右子树起点
    // 递归的对左子树和右子树进行重建
    root.left = leftLen === 0 ? undefined :Demo.rebuildTree(
      pre, 
      vin,
      // 确定前序，中序中的左子树的起点和终点(不含终点),传入索引数组
      [
        indexArr[0] + 1, 
        indexArr[0] + 1 + leftLen,
        indexArr[2],
        indexArr[2] + leftLen
      ]
    )
    root.right = rightLen === 0 ? undefined : Demo.rebuildTree(
      pre,
      vin,
      [
        indexArr[1] - rightLen,
        indexArr[1],
        indexArr[3] - rightLen,
        indexArr[3]
      ]
    )
    return root;
  }
  static test() {
    let pre = [1,2,4,7,3,5,6,8];
    let vin = [4,7,2,1,5,3,8,6];
    let root = Demo.rebuildTree(pre, vin);
    TreeNode.preRoot(root);
    console.log('前序遍历：', ...pre);
  }
}
Demo.test();

class Demo {
  static NextVinNode<T>(p:TreeNode<T>):TreeNode<T>|null {
    if(!p) return null;
    if(p.right){
      return Demo.firstVinNode(p.right)
    }else if(p.parent && p.parent.left === p) {
      return p.parent;
    }else {
      let target = p;
      while(target.parent && target.parent.left !== target){
        target = target.parent;
      }
      if(target.parent){
        return target.parent;
      }else {
        return null;
      }
    }
  }
  static firstVinNode<T>(p:TreeNode<T>):TreeNode<T>|null{
    if(!p) return null;
    if(p.left) return Demo.firstVinNode(p.left);
    return p;
  }
  static test() {
    // 本次测试用例需要重建二叉树，且二叉树中含parent父节点，不能共用NO.7中的重建方法
    // 因此暂不实现，算法已在牛客网中验证通过
  }
}

class Queue<T> {
  stack1:T[] = [];
  stack2:T[] = [];
  constructor() {

  }
  push(node:T) {
    if(this.stack2.length === 0&&this.stack1.length !== 0) {
      while(this.stack1.length > 0){
        this.stack2.push(this.stack1.pop())
      }
    }
    this.stack1.push(node);
  }
  pop(): T|undefined {
    if(this.stack2.length === 0&&this.stack1.length !== 0) {
      while(this.stack1.length > 0){
        this.stack2.push(this.stack1.pop())
      }
    }
    return this.stack2.pop()||undefined;
  }

  static test() {
    const queue = new Queue();
    let testData = [1,2,3,4,5];
    for(let i = 0; i < testData.length; i++){
      queue.push(testData[i]);
    }
    for(let i = 0; i < testData.length; i++){
      console.log(queue.pop());
    }
    console.log('result: ', testData);
  }
}

Queue.test();

class Demo {
  static fibonacci(n:number):number {
    let p = [1, 2]; // 数列约定初始值
    n = Math.floor(n);
    if(n <= 0) return -1;
    if(n < 3) return p[n -1];
    const mod = 1e9+7; // 对该数取余能保证大数相加时不溢出
    for(let i = 3; i <= n; i++) {
      let temp = (p[0] + p[1]) % mod;
      p[0] = p[1];
      p[1] = temp;
    }
    return p[1];
  }
  static test(){
    const testData = [1,2,3,5,8,13];
    let n = 6
    console.log(Demo.fibonacci(n) === testData[n - 1]);
  }
}
Demo.test();

class Demo {
  static Min(arr:number[]):number|undefined {
    if(arr.length < 2) return arr[0];
    let start = 0, mid = 0, end = arr.length - 1;
    while(arr[start] >= arr[end]){
      if(end - start === 1) {
        mid = end;
        break;
      }
      mid = Math.floor((end + start) / 2);
      if(arr[start] === arr[end] && arr[mid] === arr[start]){
        return Demo._MinInOrder(arr, start, end);
      }
      if(arr[start] <= arr[mid]){
        start = mid;
      }else if(arr[mid] <= arr[end]){
        end = mid
      }
    }
    return arr[mid];
  }
  static _MinInOrder(arr:number[], start:number, end:number):number {
    let result = arr[start];
    for(let i = start + 1; i <= end; i++){
      if(arr[i] < result){
        result = arr[i]
      }
    }
    return result;
  }
  static test(){
    const testData = [5,8,13,1,2,3];
    console.log(Demo.Min(testData));
  }
}
Demo.test();

class Demo {
  static hasPath(mat:string[][], str:string):boolean {
    if(str.length === 0 || mat.length === 0) return false;
    // debugger
    let rows = mat.length, columns = mat[0].length;
    let pathLen = 0;
    let visited:boolean[][] = new Array(rows).fill('').map(item => 
      [...new Array(columns).fill(false)]
    );
    for(let i = 0; i < rows; i++){
      for(let j = 0; j < columns; j++){
        if(Demo._hasPathCore(mat, str, i, j, visited, pathLen)) return true;
      }
    }
    return false;
  }
  static _hasPathCore(mat:string[][], str:string, i:number, j:number, visited:boolean[][], pathLen:number):boolean {
    if(pathLen >= str.length) return true;
    let result = false;
    if(i >= 0 && i < mat.length && j >= 0 && j <mat[0].length && mat[i][j] === str[pathLen] && !visited[i][j]){
      pathLen++;
      visited[i][j] = true;
      result = Demo._hasPathCore(mat, str, i, j-1, visited, pathLen) || 
      Demo._hasPathCore(mat, str, i-1, j, visited, pathLen) || 
      Demo._hasPathCore(mat, str, i, j+1, visited, pathLen) || 
      Demo._hasPathCore(mat, str, i+1, j, visited, pathLen);
      if(!result) {
        pathLen--;
        visited[i][j] = false;
      }
    }
    return result;
  }
  static test(){
    const testData = [
      ['a', 'b', 't', 'g'],
      ['c', 'f', 'c', 's'],
      ['j', 'd', 'e', 'h']
    ];
    console.log(Demo.hasPath(testData, 'abfb'));
  }
}
Demo.test();

class Demo {
  static calcSum(num:number):number{
    let result = 0;
    while(num > 0){
      result += num % 10;
      num = Math.floor(num / 10);
    }
    return result;
  }
  static inRange(matRange:number[], pos:number[], target:number) {
    let result = false;
    if(
      pos[0]<matRange[0]&&pos[0]>=0
      &&pos[1]<matRange[1]&&pos[1] >=0
      &&( Demo.calcSum(pos[0]) + Demo.calcSum(pos[1]) )<=target
    ) result = true;
    return result;
  }
  static CountBFC(matRange:number[], visited:Map<string, boolean>, pos:number[], target:number):number {
    let count = 0;
    if(Demo.inRange(matRange, pos, target)&&!visited.has(pos.toString())){
      visited.set(pos.toString(), true);
      count += 1 
        + Demo.CountBFC(matRange, visited, [pos[0]+1, pos[1]], target)
        + Demo.CountBFC(matRange, visited, [pos[0]-1, pos[1]], target)
        + Demo.CountBFC(matRange, visited, [pos[0], pos[1]+1], target)
        + Demo.CountBFC(matRange, visited, [pos[0], pos[1]-1], target);
    }
    return count;
  }
  static movingCount(target:number, rows:number, cols:number):number{
    if(target<0||rows<1||cols<1) return 0;
    // debugger
    let visited:Map<string, boolean> = new Map();
    return Demo.CountBFC([rows, cols], visited, [0,0], target);
  }
  static test(){
    console.log(Demo.movingCount(0,3,1))
  }
}
Demo.test();

class Demo {
  // 动态规划解法
  static cuttingRope(len:number):number{
    let maxLens = [0, 1, 2, 4];
    if(len < 2) return 0;
    if(len < 5) return maxLens[len - 1];
    maxLens = maxLens.concat(new Array(len - 4).fill(0));
    for(let i = 5; i <= len; i++){
      let j = 2;
      while(j <= Math.floor(i / 2)){
        let product = j*maxLens[i-j-1];
        if(maxLens[i -1] < product) maxLens[i -1] = product;
        if(maxLens[i -1] < j*(i-j)) maxLens[i -1] = j*(i - j)
        j++;
      }
    }
    return maxLens[len - 1];
  }
  // TODO:贪婪解法
  static test(){
    console.log(Demo.cuttingRope(10))
  }
}
Demo.test();

class Demo {
  // 减1算法实现
  static NumberOf1(n:number):number {
    let count = 0;
    while(n){ // n不为0 说明其二进制中还有1，继续遍历；
      count++;
      n = n&(n-1); // 每次减掉二进制中最右边的1
    }
    return count;
  }
  static test(){
    console.log(Demo.NumberOf1(-10));
  }
}
Demo.test();

class Demo {
  static Power(base:number, exponent:number):number{
    if(base === 0) return 0;
    if(exponent === 0) return 1;
    if(exponent < 0) {
      base = 1 / base;
      exponent = -exponent;
    }
    let result = 1;
    let res = base;
    while(exponent > 1){
      if(exponent % 2){
        result *= base;
      }
      exponent = Math.floor(exponent / 2);
      res *= res;
    }
    return res*result;
  }
  static test(){
    console.log(Demo.Power(2.0, -2))
  }
}
Demo.test();

export function printNumbers(n: number): number[] {
  let number = 1;
  if(n <= 0) return [];
  while(n){
    number*=10;
    n--;
  }
  let result = new Array(number - 1);
  for(let i = 1; i < number; i++){
    result[i-1] = i
  }
  return result;
}

class LinkNode<T> {
  val:T;
  next:LinkNode<T>|null
  constructor(val:T, next?:LinkNode<T>) {
    this.val = val;
    this.next = next;
  }
}

class Demo {
  static deleteNode<T>(head:LinkNode<T>, p:LinkNode<T>):LinkNode<T>{
    if(head === p){
      head = head.next;
    }
    if(!p.next){
      let parent = head;
      while(parent.next !== p){
        parent = parent.next;
      }
      if(parent) parent.next = null;
    }
    p.val = p.next.val;
    p.next = p.next.next;
    return head;
  }
  static test(){
    const testData:number[] = [4,5,1,9];
    let head = new LinkNode(testData[0]);
    let p = head;
    
    for(let i = 1; i < testData.length; i++){
      p.next = new LinkNode(testData[i]);
      p = p.next;
    }
    
    p = Demo.deleteNode(head, head.next.next);
    while(p){
      console.log(p.val);
      p = p.next;
    }
  }
}
Demo.test();

class Demo {
  static isMatch(str:string, p:string):boolean {
    if(!p&&str) return false; // 模式为空且字符串不为空时直接返回false
    return Demo.isMatchCore(str, p, [0, 0]);
  }
  static isMatchCore(str:string, p:string, indexes:number[]):boolean {
    if(!indexes) indexes = [0, 0];
    if(indexes[0] >= str.length && indexes[1] >= p.length) return true;
    if(indexes[1] >= p.length && indexes[0] < str.length) return false;
    if(indexes[1]+1 < p.length && p[indexes[1]+1] === '*'){
      if(indexes[0] >= str.length||(str[indexes[0]] !== p[indexes[1]] && p[indexes[1]] !== '.')){ // str已耗尽或(字符不匹配，则通配符匹配0次)，向后移动p指针
        return Demo.isMatchCore(str, p, [indexes[0], indexes[1]+2]); 
      }else {
        return Demo.isMatchCore(str, p, [indexes[0]+1, indexes[1]]) || // 匹配n次的情况
        Demo.isMatchCore(str, p, [indexes[0], indexes[1]+2]) || // 匹配0次的情况
        Demo.isMatchCore(str, p, [indexes[0]+1, indexes[1]+2]) // 只匹配一次的情况
      }
    }
    if(indexes[0] < str.length && (str[indexes[0]] === p[indexes[1]] || p[indexes[1]] === '.')){ // 正常匹配
      return Demo.isMatchCore(str, p, [indexes[0]+1, indexes[1]+1]);
    }else{
      return false;
    }
  }
  static test(){
    let data = 'a';
    let p = '.*..a*'
    console.log(Demo.isMatch(data,p));
  }
}
Demo.test();

class Demo {
  static isNumberic(str:string):boolean {
    if(!str) return false;
    str = str.trim(); // 祛除两侧空格
    let p = 0;
    let temp = Demo.isSignInt(str, p); // 首先检测整数
    let result = temp > 0;
    p = temp;
    if(p<str.length && !result && (str[p] === '+' || str[p] === '-')){
      p = p + 1; // 若没有匹配到整数且检测到了'+-'号则跳过该符号
    }
    if(p < str.length && str[p] === '.') { // 结合前面检测的结果检测小数部分
      temp = Demo.isUnSignInt(str, p + 1);
      result = temp > p + 1 || result;
      p = temp;
    }
    if(p < str.length && (str[p] === 'e' || str[p] === 'E')){ // 结合前面的检测结果，检测科学计数法部分
      temp = Demo.isSignInt(str, p + 1);
      result = result && temp > p + 1;
      p = temp;
    }
    return result && p >= str.length;
  }
  static isSignInt(str:string, index:number):number {
    if(!str || index >= str.length || index < 0) return index;
    if(str[index] === '-' || str[index] === '+'){
      let temp = Demo.isUnSignInt(str, index + 1);
      if(temp === index + 1) return index; // 若只有'+-'号，则整数匹配失败
      return temp;
    }
    return Demo.isUnSignInt(str, index);
  }
  static isUnSignInt(str:string, index:number):number {
    if(!str || index >= str.length || index < 0) return index;
    while(index < str.length && str[index] >= '0' && str[index] <= '9'){
      index++;
    }
    return index;
  }
  static test(){
    // debugger
    let data = '-.1';
    console.log(Demo.isNumberic(data))
  }
}
Demo.test();

class Demo {
  static reOrderArr<T>(arr:T[], fn:(T)=>boolean):T[]{
    if(arr.length < 2) return arr;
    let p1 = 0, p2 = arr.length - 1;
    while(p1 < p2) {
      if(fn(arr[p1])){
        p1++;
        continue;
      }
      if(!fn(arr[p2])) {
        p2--;
        continue;
      }
      if(!fn(arr[p1]) && fn(arr[p2])){
        let temp = arr[p1];
        arr[p1] = arr[p2];
        arr[p2] = temp;
        p1++;
        p2--;
      }
    }
    return arr
  }
  static _isEven(target:number):boolean{
    return (target & 1) === 1;
  }
  static test(){
    // debugger
    let data = [1,2,3,4,5,6,7,8,9]
    Demo.reOrderArr(data, Demo._isEven);
    console.log(data);
  }
}
Demo.test();

class ListNode<T> {
  val:T;
  next:ListNode<T>|null = null;
  constructor(val:T){
    this.val = val;
  }
}
class Demo {
  static findKthTail<T>(head:ListNode<T>, k:number):ListNode<T>|null{
    if(!head) return null
    let fast = head;
    let slow = null;
    let i = 1;
    if(i === k) slow = head;
    while(fast.next) {
      fast = fast.next;
      i++;
      if(i === k){
        slow = head;
        
      }else if(i > k) {
        slow = slow.next;
      }
    }
    return slow
  }
  static test(){
    let data = [1]
    let head = new ListNode(data[0]);
    let p = head;
    for(let i = 1; i< data.length; i++) {
      p.next = new ListNode(data[i]);
      p = p.next;
    }
    console.log(Demo.findKthTail(head, 1))
  }
}
Demo.test();

class ListNode<T> {
  val:T;
  next:ListNode<T>|null = null;
  constructor(val:T){
    this.val = val;
  }
}
class Demo {
  static EntryNodeOfLoop<T>(head:ListNode<T>):ListNode<T>|null {
    if(!head?.next) return null;
    let fast = head.next, slow = head;
    while(fast&&fast !== slow){
      slow = slow.next;
      fast = fast?.next?.next;
    }
    if(!fast) return null;
    let count = 1;
    fast = fast.next;
    while(fast !== slow){
      count++;
      fast = fast.next;
    }
    fast = head;
    slow = head;
    for(let i = count; i >0; i--){
      fast = fast.next;
    }
    while(fast!== slow){
      fast = fast.next;
      slow = slow.next;
    }
    return fast;
  }
  static test(){
    let data = [1,2,3,4,5,6,7];
    const target = 3;

    const head = new ListNode(data[0]);
    let p = head, targetNode:ListNode<number>;
    for(let i = 1; i < data.length; i++){
      p.next = new ListNode(data[i]);
      if(i === data.indexOf(target)){
        targetNode = p.next;
      }
      p = p.next;
    }
    p.next = targetNode;
    console.log(Demo.EntryNodeOfLoop(head));
  }
}
Demo.test();

class ListNode<T> {
  val:T;
  next:ListNode<T>|null = null;
  constructor(val:T){
    this.val = val;
  }
}
class Demo {
  static reverseList<T>(head:ListNode<T>):ListNode<T>{
    if(!head?.next) return head;  // 头指针为空或只有一个节点时直接返回
    let result:ListNode<T>|null = head; // 初始化result指针
    let right = head.next, left = head; // 初始化right 和left指针
    result.next = null; // 完成初始化后需要将result与后面的节点断开
    while(right){ // 当下一个指针指向末尾为空时，结束遍历
      left = right; // 因为result总和left，因此向后移动left和right指针，并开始反转操作
      right = right.next;
      left.next = result; // 添加反转节点
      result = left; // 每次遍历后result总与left指向相同节点
    }
    return result;
  }
  static test(){
    let data = [1,2,3,4,5,6,7,8,9];
    let head = new ListNode(data[0]);
    let p = head;
    for(let i = 1; i < data.length; i++){
      p.next = new ListNode(data[i]);
      p = p.next;
    }
    console.log(Demo.reverseList(head));
  }
}
Demo.test();

class ListNode<T> {
  val:T;
  next:ListNode<T>|null = null;
  constructor(val:T){
    this.val = val;
  }
}
class Demo {
  static MergeLinkList<T>(head1:ListNode<T>, head2:ListNode<T>):ListNode<T>|null {
    if(!head1||!head2) return head1 || head2;
    let p1 = head1, p2 = head2;
    if(p1.val > p2.val){
      p1 = head2;
      p2 = head1;
    }
    let result = p1, flag = true;
    let pre:ListNode<T>|null = null;
    while(p1&&p2){
      if(p1.val > p2.val){
        if(flag) {
          pre.next = p2;
          flag = false;
        }
        pre = p2;
        p2 = p2.next;
      }else {
        if(!flag) {
          pre.next = p1;
          flag = true;
        }
        pre = p1;
        p1 = p1.next;
      }
    }
    if(flag) {
      pre.next = p2;
    }else {
      pre.next = p1;
    }
    return result
  }
  static test(){
    let data1 = [1,3];
    let data2 = [2,3,5,6];
    const head1 = new ListNode(data1[0]);
    const head2 = new ListNode(data2[0]);
    let p1 = head1, p2 = head2;
    let i = 1;
    while(i < data1.length || i < data2.length){
      if(i < data1.length){
        p1.next = new ListNode(data1[i]);
        p1 = p1.next;
      }
      if(i < data2.length){
        p2.next = new ListNode(data2[i]);
        p2 = p2.next;
      }
      i++;
    }
    console.log('h1: ', head1)
    console.log('h2: ', head2)
    // debugger
    let rhead = Demo.MergeLinkList(head1, head2);
    let result = []
    while(rhead){
      result.push(rhead.val);
      rhead = rhead.next;
    }
    console.log(result);
  }
}
Demo.test();

class TreeNode<T> {
  val:T;
  left:TreeNode<T>|null = null;
  right:TreeNode<T>|null = null;
  constructor(val:T){
    this.val = val;
  }
}
class Demo {
  static isEqual(num1:number, num2:number):boolean {
    if(Math.abs(num1 - num2) < 1e-7){
      return true;
    }
    return false;
  }
  static hasSubTree<T>(RootA:TreeNode<T>, RootB:TreeNode<T>, isEqual:(n1:T, n2:T) => boolean):boolean {
    let result = false;
    if(RootA && RootB){
      if(isEqual(RootA.val, RootB.val)) result = Demo.isEqualSubTree(RootA, RootB, isEqual);
      if(!result) result = Demo.hasSubTree(RootA.left, RootB, isEqual);
      if(!result) result = Demo.hasSubTree(RootA.right, RootB, isEqual);
    } 
    return result
  }
  static isEqualSubTree<T>(p1:TreeNode<T>, p2:TreeNode<T>, isEqual:(p1:T, p2:T) => boolean):boolean {
    let result = false;
    if(!p2) return true;
    if(!p1) return false;
    if(!isEqual(p1.val, p2.val)) return false;
    return Demo.isEqualSubTree(p1.left, p2.left, isEqual) && Demo.isEqualSubTree(p1.right, p2.right, isEqual);
    
  }
  static test(){
    const rootA = new TreeNode(8);
    const rootB = new TreeNode(8);
    rootA.left = new TreeNode(8);
    rootA.right = new TreeNode(7);
    rootA.left.left = new TreeNode(9);
    rootA.left.right = new TreeNode(2);
    rootA.left.right.left = new TreeNode(4);
    rootA.left.right.right = new TreeNode(7);
    rootB.left = new TreeNode(9);
    rootB.right = new TreeNode(2);
    console.log(Demo.hasSubTree(rootA, rootB, Demo.isEqual));
  }
}
Demo.test();

class TreeNode<T> {
  val:T;
  left:TreeNode<T>|null = null;
  right:TreeNode<T>|null = null;
  constructor(val:T){
    this.val = val;
  }
}
class Demo {
  static mirrorTree<T>(pRoot:TreeNode<T>):TreeNode<T>|null{
    if(!pRoot) return pRoot;
    if(!pRoot.left&&!pRoot.right) return pRoot;
    let temp = pRoot.left;
    pRoot.left = pRoot.right;
    pRoot.right = temp;
    Demo.mirrorTree(pRoot.right);
    Demo.mirrorTree(pRoot.left);
    return pRoot;
  }
  static test(){
    const rootA = new TreeNode(8);
    rootA.left = new TreeNode(8);
    rootA.right = new TreeNode(7);
    rootA.left.left = new TreeNode(9);
    rootA.left.right = new TreeNode(2);
    rootA.left.right.left = new TreeNode(4);
    rootA.left.right.right = new TreeNode(7);
    console.log(Demo.mirrorTree(rootA));
  }
}
Demo.test();

class TreeNode<T> {
  val:T;
  left:TreeNode<T>|null = null;
  right:TreeNode<T>|null = null;
  constructor(val:T){
    this.val = val;
  }
}
class Demo {
  static isSymmetric<T>(pRoot:TreeNode<T>):boolean {
    return  Demo.isSymmetricCore(pRoot, pRoot);
  }
  static isSymmetricCore<T>(p1:TreeNode<T>, p2:TreeNode<T>):boolean {
    if(!p1&&!p2) return true;
    if(!p1||!p2) return false;
    if(p1.val !== p2.val) return false;
    return Demo.isSymmetricCore(p1.left, p2.right) && Demo.isSymmetricCore(p1.right, p2.left);
  }
  static test(){
    const rootA = new TreeNode(8);
    rootA.left = new TreeNode(8);
    rootA.right = new TreeNode(7);
    rootA.left.left = new TreeNode(9);
    rootA.left.right = new TreeNode(2);
    rootA.left.right.left = new TreeNode(4);
    rootA.left.right.right = new TreeNode(7);
    console.log(Demo.isSymmetric(rootA));
  }
}
Demo.test();