题目描述补充

题目：寻找BST（二叉搜索树）的Modes（众数）

给定一棵二叉搜索树（BST），其中每个节点的值都是唯一的。我们需要找出这棵树中出现频率最高的元素（们），这些元素被称为众数。由于BST的性质（左子树的所有节点的值都小于其父节点的值，右子树的所有节点的值都大于其父节点的值），我们可以利用这一性质来优化搜索过程。

注意：BST中可能有多个众数，它们的出现频率相同且为该树中最高的频率。

示例

考虑以下BST：

        5
       / \
      2   7
     / \
    1   3

在这个BST中，没有众数，因为每个数字只出现一次。

但如果BST是这样的：

        5
       / \
      2   7
     / \   \
    1   3   7

那么众数是7，因为它出现了两次，而其他数字只出现了一次。

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代码示例

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代码示例

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);

码小课网站中有更多关于二叉树遍历、搜索和算法优化的相关内容分享给大家学习。