当前位置： 面试刷题>> 寻找BST的modes (经典算法题500道)
### 题目描述补充
题目：**寻找BST（二叉搜索树）的Modes（众数）**
给定一棵二叉搜索树（BST），其中每个节点的值都是唯一的。我们需要找出这棵树中出现频率最高的元素（们），这些元素被称为众数。由于BST的性质（左子树的所有节点的值都小于其父节点的值，右子树的所有节点的值都大于其父节点的值），我们可以利用这一性质来优化搜索过程。
**注意**：BST中可能有多个众数，它们的出现频率相同且为该树中最高的频率。
### 示例
考虑以下BST：
```
5
/ \
2 7
/ \
1 3
```
在这个BST中，没有众数，因为每个数字只出现一次。
但如果BST是这样的：
```
5
/ \
2 7
/ \ \
1 3 7
```
那么众数是7，因为它出现了两次，而其他数字只出现了一次。
### PHP代码示例
```php
class TreeNode {
public $val;
public $left;
public $right;
function __construct($val = 0, $left = null, $right = null) {
$this->val = $val;
$this->left = $left;
$this->right = $right;
}
}
function findMode(TreeNode $root) {
$countMap = [];
$maxCount = 0;
$modes = [];
// 中序遍历统计每个元素的出现次数
function inorderTraversal($node, &$countMap, &$maxCount, &$modes) {
if ($node === null) return;
inorderTraversal($node->left, $countMap, $maxCount, $modes);
if (!isset($countMap[$node->val])) {
$countMap[$node->val] = 1;
} else {
$countMap[$node->val]++;
}
if ($countMap[$node->val] > $maxCount) {
$maxCount = $countMap[$node->val];
$modes = [$node->val];
} elseif ($countMap[$node->val] == $maxCount) {
$modes[] = $node->val;
}
inorderTraversal($node->right, $countMap, $maxCount, $modes);
}
inorderTraversal($root, $countMap, $maxCount, $modes);
return $modes;
}
// 示例用法
$root = new TreeNode(5);
$root->left = new TreeNode(2);
$root->right = new TreeNode(7);
$root->left->left = new TreeNode(1);
$root->left->right = new TreeNode(3);
$root->right->right = new TreeNode(7);
$modes = findMode($root);
print_r($modes);
```
### Python代码示例
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def findMode(root):
count_map = {}
max_count = 0
modes = []
def inorder_traversal(node):
nonlocal count_map, max_count, modes
if not node:
return
inorder_traversal(node.left)
if node.val not in count_map:
count_map[node.val] = 1
else:
count_map[node.val] += 1
if count_map[node.val] > max_count:
max_count = count_map[node.val]
modes = [node.val]
elif count_map[node.val] == max_count:
modes.append(node.val)
inorder_traversal(node.right)
inorder_traversal(root)
return modes
# 示例用法
root = TreeNode(5)
root.left = TreeNode(2)
root.right = TreeNode(7)
root.left.left = TreeNode(1)
root.left.right = TreeNode(3)
root.right.right = TreeNode(7)
modes = findMode(root)
print(modes)
```
### JavaScript代码示例
```javascript
function TreeNode(val, left, right) {
this.val = (val===undefined ? 0 : val);
this.left = (left===undefined ? null : left);
this.right = (right===undefined ? null : right);
}
function findMode(root) {
let countMap = {};
let maxCount = 0;
let modes = [];
function inorderTraversal(node) {
if (!node) return;
inorderTraversal(node.left);
if (!countMap[node.val]) {
countMap[node.val] = 1;
} else {
countMap[node.val]++;
}
if (countMap[node.val] > maxCount) {
maxCount = countMap[node.val];
modes = [node.val];
} else if (countMap[node.val] === maxCount) {
modes.push(node.val);
}
inorderTraversal(node.right);
}
inorderTraversal(root);
return modes;
}
// 示例用法
const root = new TreeNode(5);
root.left = new TreeNode(2);
root.right = new TreeNode(7);
root.left.left = new TreeNode(1);
root.left.right = new TreeNode(3);
root.right.right = new TreeNode(7);
const modes = findMode(root);
console.log(modes);
```
**码小课**网站中有更多关于二叉树遍历、搜索和算法优化的相关内容分享给大家学习。