JavaScript solution, traverse the tree only once


  • 0

    Hi @StefanPochmann, your solution (https://discuss.leetcode.com/topic/77335/proper-o-1-space) is brilliant! I modified the handleValue a little bit so that we can traverse the tree only once. I really like the way how you handle the current value, current count, modes array and mode count, genius!

    /**
     * @param {TreeNode} root
     * @return {number[]}
     */
    const findMode = root => {
      const handleValue = val => {
        // handle current count
        if (val !== currVal) {
          currVal = val;
          currCount = 0;
        }
        currCount++;
    
        if (currCount > maxCount) {
          // found a new mode
          maxCount = currCount;
          modeCount = 1;
          modes[0] = currVal;
        } else if (currCount === maxCount) {
          // found a mode with same count
          modes[modeCount] = currVal;
          modeCount++;
        }
      };
    
      const inorder = node => {
        if (!node) return;
    
        inorder(node.left);
        handleValue(node.val);
        inorder(node.right);
      };
    
      let currVal = null;
      let currCount = 0;
      let maxCount = 0;
      let modeCount = 0;
    
      const modes = [];
    
      inorder(root);
    
      return modes.slice(0, modeCount);
    };
    

    And here is the result of the JavaScript runtime:
    alt text


  • 1

    Hmm, ok, but you take more than O(1) extra space, and that was pretty much the whole point of mine, and the only reason I have two passes :-)


Log in to reply
 

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