求树中最大同值连通节点区域规模的算法问询（面试题）

问题回顾 #

给定一棵数值树，求解其中由同值节点构成的最大连通区域的规模。示例树结构如下：

3
   /   \
  3     3
 / \   / \
1  2  3  4

示例答案为4，因为存在4个相连的3组成的连通区域。

核心解法思路 #

这题我之前面试也碰到过，当时琢磨了好一会儿，核心是用后序遍历来处理——得先摸清楚左右子树的同值连通情况，才能算出当前节点能参与的最大区域：

• 对每个节点，递归计算左子树中与当前节点值相同的连通长度left_len，右子树同理得到right_len
• 当前节点所在的同值连通区域总规模是 1 + left_len + right_len（如果子节点值和当前节点不同，对应的长度直接取0）
• 用一个变量全程跟踪遍历过程中出现的最大规模值
• 注意递归返回的是当前节点作为端点的最长同值连通长度（也就是1 + max(left_len, right_len)），而不是当前区域的总规模——这样父节点才能正确判断是否能和当前节点连成更大的区域

代码实现（Python） #

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

def largestSameValueSubtree(root):
    max_size = 0
    
    def post_order(node):
        nonlocal max_size
        if not node:
            return 0
        
        # 先递归处理左右子树，拿到子树的同值连通长度
        left = post_order(node.left)
        right = post_order(node.right)
        
        # 判断当前节点与左/右子树是否同值，计算连通长度
        current_left = left + 1 if (node.left and node.left.val == node.val) else 0
        current_right = right + 1 if (node.right and node.right.val == node.val) else 0
        
        # 计算当前节点所在的同值区域总规模
        current_total = 1
        if current_left > 0:
            current_total += current_left
        if current_right > 0:
            current_total += current_right
        
        # 更新全局记录的最大规模
        if current_total > max_size:
            max_size = current_total
        
        # 返回当前节点能向父节点延伸的最长同值长度
        return max(current_left, current_right) + 1 if (current_left or current_right) else 1
    
    post_order(root)
    return max_size

# 构建示例树并测试
root = TreeNode(3)
root.left = TreeNode(3)
root.right = TreeNode(3)
root.left.left = TreeNode(1)
root.left.right = TreeNode(2)
root.right.left = TreeNode(3)
root.right.right = TreeNode(4)

print(largestSameValueSubtree(root))  # 输出：4

代码解释 #

• 用nonlocal变量max_size全程记录遍历中找到的最大同值连通区域规模
• 后序遍历的顺序保证我们先处理完子节点，再基于子节点的结果计算当前节点的情况
• current_left和current_right分别判断当前节点与左右子树的同值性，确定连通长度
• 每次计算完当前区域的总规模后，立即更新全局最大值
• 返回的长度是当前节点能向父节点延伸的最长同值链，确保父节点可以正确计算更大的连通区域

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