2020-06-21 501. Find Mode in Bin

https://leetcode.com/problems/find-mode-in-binary-search-tree/submissions/

My answer / AC

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var findMode = function(root) {
    let map = {};
    let dfs = function(node) {
        if(!node) return;
        if(map[node.val]) 
            map[node.val]++;
        else 
            map[node.val] = 1;
        
        dfs(node.left);
        dfs(node.right);
        
    }
    dfs(root);
    if(Object.keys(map).length==0) return [];
    let max = Object.values(map).reduce((a,v)=>a>v?a:v);
    return Object.entries(map).filter(e=>e[1]===max).map(e=>e[0]);
};

为什么这道easy的题我却没有觉得很简单！
思路简单来说就是二叉树哦遍历，并且找到value等于最大值的那些个组合。

Best answer

var findMode = function(root) {
    var mode = [], 
        curNodeVal = NaN, 
        curNodeCount = 0, 
        maxCount = -Infinity;
    
    var inorder = function(root) {
        if (!root) return;
        inorder(root.left);
        curNodeCount = (root.val === curNodeVal ? curNodeCount : 0) + 1;
        curNodeVal = root.val;
        if (curNodeCount > maxCount) {
            mode = [root.val];
            maxCount = curNodeCount;
        } else if (curNodeCount === maxCount) {
            mode.push(root.val);
        }
        inorder(root.right);
    }
    inorder(root);
    return mode;
}

整个curNodeCount来数value等于curNodeVal的节点，剩下的就和dfs一个意思。

Recap

深度遍历的新实践，手动来实现最大值的add和push