[H] 297. 序列化與反序列化二元樹 (Serialize and Deserialize Binary Tree)

輸入：root = [1,2,3,null,null,4,5]
輸出：[1,2,3,null,null,4,5]

輸入：root = []
輸出：[]

// declare a TreeCodec class including following two functions
 
/*
 * Encodes a tree to a single string.
 */
function serialize(root: TreeNode | null): string {
  // if root is null, return empty string
  // declare a result string array
  // declare a queue to do level order traversal, init with root value
 
  // run a while loop when queue is not empty
    // dequeue to get current node
    // if current node not null
      // push value into result
      // enqueue left node and right node
    // push null value
 
  // remove redundant null value at tail
  // return serialized string by joining with `,`
}
 
/*
 * Decodes your encoded data to tree.
 */
function deserialize(data: string): TreeNode | null {
  // if data is empty string, return null
 
  // split string by `,`
  // transform each value to null or number
  // declare result tree
  // declare a queue, init with first node
 
  // run a while loop when queue is not empty
    // dequeue current node
    // assign next value as left node if it's not null
    // assign next value as right node if it's not null
 
  // return result tree
}

// declare a TreeCodec class including following two functions
class TreeCodec {
  /*
   * Encodes a tree to a single string.
   */
  serialize(root: TreeNode | null): string {
    // if root is null, return empty string
    if (root === null) {
      return '';
    }
 
    // declare a result string array
    const result: string[] = [];
 
    // declare a queue to do level order traversal, init with root value
    const queue: (TreeNode | null)[] = [root];
 
    // run a while loop when queue is not empty
    while (queue.length > 0) {
      // dequeue to get current node
      const currentNode = queue.shift();
 
      // if current node not null
      if (currentNode) {
        // push value into result
        result.push(currentNode.val.toString());
        // enqueue left node and right node
        queue.push(currentNode.left);
        queue.push(currentNode.right);
      } else {
        result.push('n');
      }
    }
 
    // remove redundant null value at tail
    while (result[result.length - 1] === 'n') {
      result.pop();
    }
 
    // return serialized string by joining with `,`
    return result.join(',');
  }
 
  /*
   * Decodes your encoded data to tree.
   */
  deserialize(data: string): TreeNode | null {
    // if data is empty string, return null
    if (data === '') {
      return null;
    }
 
    // split string by `,`
    // transform each value to null or number
    const values = data.split(',').map((v) => (v === 'n' ? null : Number(v)));
 
    // preventing wrong data format with empty root value
    if (typeof values[0] !== 'number') {
      throw new Error('wrong input data');
    }
 
    // declare result tree
    const root = new TreeNode(values[0]);
    // declare a queue, init with first node
    const queue = [root];
    let currentIndex = 1;
 
    // run a while loop when queue is not empty
    while (queue.length > 0) {
      // dequeue current node
      const node = queue.shift() as TreeNode;
      // assign next value as left node if it's not null
      if (typeof values[currentIndex] === 'number') {
        node.left = new TreeNode(values[currentIndex]!);
        queue.push(node.left);
      }
      currentIndex++;
 
      // assign next value as right node if it's not null
      if (typeof values[currentIndex] === 'number') {
        node.right = new TreeNode(values[currentIndex]!);
        queue.push(node.right);
      }
      currentIndex++;
    }
 
    // return result tree
    return root;
  }
}

describe('Serialize and Deserialize Binary Tree', () => {
  const codec = new TreeCodec();
 
  it('should correctly serialize and deserialize for example 1', () => {
    const root = new TreeNode(
      1,
      new TreeNode(2),
      new TreeNode(3, new TreeNode(4), new TreeNode(5))
    );
    const serialized = codec.serialize(root);
    const deserialized = codec.deserialize(serialized);
 
    expect(serialized).toEqual('1,2,3,n,n,4,5');
    expect(deserialized).toEqual(root);
  });
 
  it('should handle empty tree for example 2', () => {
    const root = null;
    const serialized = codec.serialize(root);
    const deserialized = codec.deserialize(serialized);
 
    expect(serialized).toEqual('');
    expect(deserialized).toBeNull();
  });
 
  it('should handle tree with only leftmost node in the last level', () => {
    const root = new TreeNode(
      1,
      new TreeNode(2, new TreeNode(4)),
      new TreeNode(3)
    );
    const serialized = codec.serialize(root);
 
    expect(serialized).toEqual('1,2,3,4');
  });
 
  it('should handle tree with negative values', () => {
    const root = new TreeNode(
      -1,
      new TreeNode(-2),
      new TreeNode(-3, new TreeNode(-4), new TreeNode(-5))
    );
    const serialized = codec.serialize(root);
    const deserialized = codec.deserialize(serialized);
 
    expect(serialized).toEqual('-1,-2,-3,n,n,-4,-5');
    expect(deserialized).toEqual(root);
  });
 
  it('should handle tree with root value of 0', () => {
    const root = new TreeNode(0, new TreeNode(-1), new TreeNode(1));
    const serialized = codec.serialize(root);
    const deserialized = codec.deserialize(serialized);
 
    expect(serialized).toEqual('0,-1,1');
    expect(deserialized).toEqual(root);
  });
 
  it('should handle tree with 10000 nodes having only left children', () => {
    const root = new TreeNode(1);
    let current = root;
 
    for (let i = 2; i <= 10000; i++) {
      const newNode = new TreeNode(i);
      current.left = newNode;
      current = newNode;
    }
 
    const serialized = codec.serialize(root);
    const deserialized = codec.deserialize(serialized);
 
    expect(serialized.startsWith('1,2,n,3,n,4,n')).toBeTruthy();
    expect(deserialized).toEqual(root);
  });
 
  it('should handle a complete binary tree with lots of nodes', () => {
    const createCompleteBinaryTree = (n: number): TreeNode | null => {
      if (n === 0) return null;
      const nodes = Array.from({ length: n }, (_, i) => new TreeNode(i + 1));
      for (let i = 0; i < Math.floor(n / 2); i++) {
        if (2 * i + 1 < n) nodes[i].left = nodes[2 * i + 1];
        if (2 * i + 2 < n) nodes[i].right = nodes[2 * i + 2];
      }
      return nodes[0];
    };
 
    const root = createCompleteBinaryTree(10000);
    const serialized = codec.serialize(root);
    const deserialized = codec.deserialize(serialized);
 
    expect(deserialized).toEqual(root);
  });
});