/**
 * 二叉树节点的可选类型（节点实例 或 null）
 * @template T 节点值的类型，与 TreeNode<T> 保持一致
 * @description 简化 TreeNode<T> | null 的重复书写，提升代码可读性
 */
export type NodeType<T> = TreeNode<T> | null;

/**
 * 二叉树节点类（泛型支持任意数据类型）
 * @template T 节点存储的值的类型
 */
export class TreeNode<T> {
  /**
   * 二叉树节点构造函数
   * @param value 节点存储的值
   * @param left 左子节点（默认为 null）
   * @param right 右子节点（默认为 null）
   */
  constructor(
    public value: T,
    public left: NodeType<T> = null,
    public right: NodeType<T> = null
  ) {}
}

const preOrder = (root: NodeType<string>) => {
  if (root === null) return;
  // 先访问根节点
  console.log('pre:' + root.value + '\t');
  preOrder(root.left);
  preOrder(root.right);

};

const inOrder = (root: NodeType<string>) => {
  if (root === null) return;
  inOrder(root.left);
  // 左子树遍历后访问根节点
  console.log('in:' + root.value + '\t');
  inOrder(root.right);
};

const postOrder = (root: NodeType<string>) => {
  if (root === null) return;
  postOrder(root.left);
  postOrder(root.right);
  // 最后访问根节点
  console.log('pre:' + root.value + '\t');
};

/**
 * Generate binary tree from preOrderList and inOrderList
 * @param preOrderList
 * @param inOrderList
 * @returns root
 */
function buildTree<T>(preOrderList: Array<T>, inOrderList: Array<T>): NodeType<T> {
  // the precondition of rebuilding Binary Tree
  if (!preOrderList.length || !inOrderList.length) return null;
  if (preOrderList.length !== inOrderList.length)
    throw new Error('The lengths of preOrderList and inOrderList must be equal.');
  // first element of preOrderList is root
  const rootVal = preOrderList[0];
  const root = new TreeNode<T>(rootVal);

  // the length of preOrderList equal to 1 (the end of recursion)
  if (preOrderList.length === 1) return root;

  // find the rootVal' s index in inOrderList
  const inOrderListRootIdx = inOrderList.indexOf(rootVal);

  // Error handler
  if (inOrderListRootIdx === -1) {
    throw new Error(`Root value ${rootVal} not found in inOrderList`);
  }

  // divide inOrderList: left & right
  const leftInOrderList = inOrderList.slice(0, inOrderListRootIdx);
  const rightInOrderList = inOrderList.slice(inOrderListRootIdx + 1);

  // divide preOrderList: left & right
  // the size of left tree equals the length of leftInOrderList
  const leftSubTreeLen = leftInOrderList.length;
  const leftPreOrderList = preOrderList.slice(1, leftSubTreeLen + 1);
  const rightPreOrderList = preOrderList.slice(leftSubTreeLen + 1);
  
  // Recursively call the buildTree method
  root.left = buildTree(leftPreOrderList, leftInOrderList);
  root.right = buildTree(rightPreOrderList, rightInOrderList);

  return root;

}

function buildTree<T>(postOrderList: Array<T>, inOrderList: Array<T>): NodeType<T> {
  if (!postOrderList.length || !inOrderList.length) return null;
  if (postOrderList.length !== inOrderList.length)
    throw new Error('The lengths of postOrderList and inOrderList must be equal.');
  const rootVal = postOrderList[postOrderList.length - 1];
  const root = new TreeNode<T>(rootVal);
  if (postOrderList.length === 1) return root;
  const inOrderRootIdx = inOrderList.indexOf(rootVal);

  if (inOrderRootIdx === -1) {
    throw new Error(`Value ${rootVal} not found in inOrderList. Failed to construct binary tree`);
  }

  const leftInOrderList = inOrderList.slice(0, inOrderRootIdx);
  const rightInOrderList = inOrderList.slice(inOrderRootIdx + 1);

  const leftTreeSize = leftInOrderList.length;
  const leftPostOrderList = postOrderList.slice(0, leftTreeSize);
  const rightPostOrderList = postOrderList.slice(leftTreeSize, postOrderList.length - 1);

  root.left = buildTree(leftPostOrderList, leftInOrderList);
  root.right = buildTree(rightPostOrderList, rightInOrderList);
  return root;
}

/**
 * @param root
 * @param target
 * @returns isFind
 */
function depthSearch(root: TreeNode, target: string): boolean {
  if (root === null) return false;
  if (root.value === target) return true;

  const left = depthSearch(root.left!, target);
  const right = depthSearch(root.right!, target);
  return left || right;
}

/**
 * @param root
 * @param target
 * @returns isFind
 */
function breadthFirstSearch(root: TreeNode, target: string): boolean {
  if (root === null) return false;
  const queue: Array<TreeNode> = [];
  queue.push(root);

  while (queue.length > 0) {
    const currRoot = queue.shift();
    if (!currRoot) break;
    if (currRoot.value === target) return true;
    if (currRoot.left !== null) queue.push(currRoot.left);
    if (currRoot.right !== null) queue.push(currRoot.right);
  }
  return false;
}

/**
 * @param treeA
 * @param treeB
 * @returns isEqual
 */
const compareTree = (treeA: TreeNode | null, treeB: TreeNode | null): boolean => {
  // 终止条件1：两个节点都为空 → 相等
  if (treeA === null && treeB === null) return true;
  // 终止条件2：一个为空、一个不为空 → 不相等
  if (treeA === null || treeB === null) return false;
  // 终止条件3：节点值不相等 → 不相等
  if (treeA.value !== treeB.value) return false;
  
  // 二叉树可能有扭转情况
  const res1 = compareTree(treeA?.left!, treeB?.left!) && compareTree(treeA?.right!, treeB?.right!);
  const res2 = compareTree(treeA?.left!, treeB?.right!) && compareTree(treeB?.left!, treeA?.right!);
  return res1 || res2;
};

// 改变
const enum ChangeType {
  DEL = '删除',
  ADD = '增加',
  UPD = '修改',
}

// 父节点不变的节点类型
type InfoWithParent = {
  type: ChangeType;
  origin: NodeType;
  now: NodeType;
  parent: NodeType; // 单 parent 属性
};
// 父节点改变的节点类型
type InfoWithOldNewParent = {
  type: ChangeType;
  origin: NodeType;
  now: NodeType;
  oldParent: NodeType; // 旧父节点
  newParent: NodeType; // 新父节点
};
// 节点信息类型
type info = InfoWithOldNewParent | InfoWithParent;
// 二叉树节点类型
type NodeType = TreeNode | null;

// 二叉树对比
function diffTree(treeA: NodeType, treeB: NodeType): Array<info> {
  // 收集差异信息的数组
  const diffList = new Array<info>();
  // 二叉树对比主方法
  function recursiveDiff(
    treeA: NodeType,
    treeB: NodeType,
    rootA: NodeType = null,
    rootB: NodeType = null
  ) {
    //  说明两颗树引用是相同的（包括都为 null），说明没有差异
    if (treeA === treeB) return;
    //  新增
    if (treeA === null && treeB !== null)
      return handleDiff(ChangeType.ADD, treeA, treeB, rootA, rootB, diffList);
    //  删除
    if (treeA !== null && treeB === null)
      return handleDiff(ChangeType.DEL, treeA, treeB, rootA, rootB, diffList);
    //  修改: 对比值是否变化
    if (treeA?.value !== treeB?.value)
      handleDiff(ChangeType.UPD, treeA, treeB, rootA, rootB, diffList);

    // 递归左右子树
    recursiveDiff(treeA?.left!, treeB?.left!, treeA, treeB);
    recursiveDiff(treeA?.right!, treeB?.right!, treeA, treeB);
  }
  // 差异信息收集方法
  function handleDiff(
    type: ChangeType,
    oldNode: NodeType,
    newNode: NodeType,
    oldParent: NodeType,
    newParent: NodeType,
    diffList: info[]
  ) {
    const oldParentVal = oldParent?.value;
    const newParentVal = newParent?.value;
    // 先比较父节点是否变化
    if (oldParentVal === newParentVal) {
      diffList.push({
        type,
        origin: oldNode,
        now: newNode,
        parent: newParent,
      });
    } else {
      diffList.push({
        type,
        origin: oldNode,
        now: newNode,
        oldParent,
        newParent,
      });
    }
  }
  recursiveDiff(treeA, treeB);
  return diffList;
}