如何用Python实现查找树中跨层级出现最频繁的节点？

Hey there! You’re absolutely right to go with level-order traversal (BFS) for this problem—let’s refine it to track which levels each node value appears in, then pick the value that shows up in the most unique levels.

Step 1: Clarify the Requirement #

First, let’s make sure we’re on the same page: we need to count how many distinct levels a node value appears in, not the total number of times the node exists. For example, if a is present in levels 0, 1, and 2 (even if there are multiple as in one level), it counts as 3 occurrences, which makes it the answer in your example.

Step 2: Implementation Approach #

Here’s the plan:

• Use BFS to traverse the tree level by level—this naturally lets us track the current level number as we go.
• Maintain a dictionary where each key is a node value, and the value is a set of levels it’s appeared in. Using a set ensures we don’t count the same level multiple times for duplicate nodes in that level.
• After traversal, calculate the size of each set (this is the number of distinct levels for that value) and find the value with the largest size.

Step 3: Python Code #

First, let’s complete the TreeNode class (I’ll fill in the missing left/right attributes):

class TreeNode:
    def __init__(self, data=None):
        self.data = data
        self.left = None
        self.right = None

Now, here’s the function to solve the problem:

from collections import deque, defaultdict

def find_most_frequent_level_node(root):
    if not root:
        return None  # Handle empty tree case
    
    # Key: node data, Value: set of levels the data appears in
    value_levels = defaultdict(set)
    # Queue for BFS: each element is (current_node, current_level)
    queue = deque([(root, 0)])
    
    while queue:
        node, level = queue.popleft()
        # Add current level to the set for this node's data
        value_levels[node.data].add(level)
        
        # Enqueue left and right children if they exist
        if node.left:
            queue.append((node.left, level + 1))
        if node.right:
            queue.append((node.right, level + 1))
    
    # Now find the value with the maximum number of distinct levels
    max_level_count = -1
    result = None
    for value, levels in value_levels.items():
        level_count = len(levels)
        if level_count > max_level_count:
            max_level_count = level_count
            result = value
    
    return result

Step 4: Test with Your Example #

Let’s build the tree from your example to verify:

# Build the tree:
# Level 0: a
# Level 1: c, a
# Level 2: c, a, b, c
root = TreeNode('a')
root.left = TreeNode('c')
root.right = TreeNode('a')
root.left.left = TreeNode('c')
root.left.right = TreeNode('a')
root.right.left = TreeNode('b')
root.right.right = TreeNode('c')

# Test the function
print(find_most_frequent_level_node(root))  # Output: 'a'

Explanation #

• BFS Traversal: We use a queue to process each node along with its current level. This guarantees we process nodes level by level.
• Set for Levels: Using a set ensures that even if multiple nodes with the same value exist in the same level, we only count that level once for the value.
• Finding the Result: After collecting all level data, we iterate through the dictionary to find the value with the largest set size (most distinct levels).

内容的提问来源于stack exchange，提问作者Dawn17