LeetCode 笔记

# 501.二叉搜索树中的众数

# 题目

给定一个有相同值的二叉搜索树（BST，是一颗有序树：右 > 中 > 左），找出 BST 中的所有众数（出现频率最高的元素）。

假定 BST 有如下定义：

  • 结点左子树中所含结点的值小于等于当前结点的值
  • 结点右子树中所含结点的值大于等于当前结点的值
  • 左子树和右子树都是二叉搜索树

例如：给定 BST [1,null,2,2],

   1
    \
     2
    /
   2

返回[2]，如果众数超过1个，不需考虑输出顺序
链接：https://leetcode-cn.com/problems/find-mode-in-binary-search-tree/ (opens new window)

# 答案

该题主要考察了二叉树的遍历，在使用 中序遍历 遍历 二叉搜索树 时是从小到大的有序遍历，这样遍历重复的数字总是挨着的，我们便可以记录出现的次数来找出最大出现次数的节点。

/**
 * 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 base;
  let count = 0;
  let maxCount = 0;
  let res = [];

  const update = function(val) {
    if (val === base) {
      count++;
    } else {
      count = 1;
      base = val;
    }
    if (count === maxCount) {
      res.push(val);
    }
    if (count > maxCount) {
      maxCount = count;
      res = [val];
    }
  }

  // 中序遍历二叉搜索树是有序的
  const traversal = function(node) {
    if (!node) return;
    
    if (node.left) {
      traversal(node.left);
    }
    update(node.val);
    if (node.right) {
      traversal(node.right);
    }
  }
  
  traversal(root);

  return res;
};

# 508.出现次数最多的子树元素和

# 题目

给你一个二叉树的根结点，请你找出出现次数最多的子树元素和。一个结点的「子树元素和」定义为以该结点为根的二叉树上所有结点的元素之和（包括结点本身）。

你需要返回出现次数最多的子树元素和。如果有多个元素出现的次数相同，返回所有出现次数最多的子树元素和（不限顺序）。

例如，输入：

  5
 /  \
2   -5

返回 [2]，只有 2 出现两次，-5 只出现 1 次。
链接：https://leetcode-cn.com/problems/most-frequent-subtree-sum/ (opens new window)

# 答案

根据题意，我们可以很快的想到通过后序遍历来记录每一个子树元素和，之后通过 map 统计出现最多次数即可

/**
 * 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 findFrequentTreeSum = function(root) {
  const map = {};
  const res = [];

  // 后续遍历二叉树
  const traversal = function(node) {
    if (!node) return 0;
    let leftSum = 0;
    let rightSum = 0;
    if (node.left) {
      leftSum = traversal(node.left);
    }
    if (node.right) {
      rightSum = traversal(node.right);
    }
    const res = node.val + leftSum + rightSum;
    // 将根节点及其子节点的值存入 map
    map[res] = (map[res] || 0) + 1;
    return res;
  }

  traversal(root);

  const max = Math.max(...Object.values(map));
  Object.keys(map).forEach(key => {
    if (max === map[key]) {
      res.push(key);
    }
  });

  return res;
};

← 链表 →