[JavaScript] LeetCode fails to print array of null (e.g. [ 1, null ])


  • -1
    H

    I found a bug caused by LeetCode's judging engine when using JavaScript to solve this problem.
    Running the code snippet below prints [1, []] instead of [1, null] and this made my solution failed for the testcase [2,2,2,3,null,3,null]

    const findDuplicateSubtrees = function (root) {
      return [1, null];
    }
    

    My solution:

    function printTreeToArray(root) {
      const queue = [root];
      const res = [];
      while (queue.length > 0) {
        const node = queue.shift();
        if (node !== null) {
          res.push(node.val);
          if (node.left === null && node.right === null) continue;
          queue.push(node.left);
          queue.push(node.right);
        } else {
          res.push(node);
        }
      }
      return res;
    }
    
    function traverseTree(root, cb) {
      if (root === null) return 'null';
      const key = `${root.val},${traverseTree(root.left, cb)},${traverseTree(root.right, cb)}`;
      return cb(key, root);
    }
    
    /**
     * @param {TreeNode} root
     * @return {TreeNode[]}
     */
    const findDuplicateSubtrees = function (root) {
      const res = [];
      const map = new Map();
    
      traverseTree(root, (key, node) => {
        const count = map.get(key);
        if (count === undefined) {
          map.set(key, 1);
        } else if (count === 1) {
          res.push(printTreeToArray(node));
          map.set(key, 2);
        }
        return key;
      });
    
      return res;
    };
    

  • 1

    @hieudo said in [JavaScript] LeetCode fails to print array of null (e.g. [ 1, null ]):

    I found a bug caused by LeetCode's judging engine when using JavaScript to solve this problem.
    Running the code snippet below prints [1, []] instead of [1, null] and this made my solution failed for the testcase [2,2,2,3,null,3,null]

    const findDuplicateSubtrees = function (root) {
      return [1, null];
    }
    

    You return something broken (1 is not a TreeNode) and then blame the judge for anything?

    Also, [] is the correct serialization of the empty tree.
    https://leetcode.com/faq/#binary-tree


  • 0
    H

    @ManuelP It's my bad. I was trying to serialize each subtree I found to an array which was a wrong idea since what the problem wants is an array of TreeNode and LeetCode will handle the serialization. Thanks for your help, really appreciate it. :)

    Here is my accepted solution.

    function traverseTree(root, cb) {
      if (root === null) return 'null';
      const key = `${root.val},${traverseTree(root.left, cb)},${traverseTree(root.right, cb)}`;
      return cb(key, root);
    }
    
    /**
     * @param {TreeNode} root
     * @return {TreeNode[]}
     */
    const findDuplicateSubtrees = function (root) {
      const res = [];
      const map = new Map();
    
      traverseTree(root, (key, node) => {
        const count = map.get(key);
        if (count === undefined) {
          map.set(key, 1);
        } else if (count === 1) {
          res.push(node);
          map.set(key, 2);
        }
        return key;
      });
    
      return res;
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.