LeetCode第250题：统计同值子树

问题描述

给定一个二叉树，统计该二叉树数值相同的子树个数。

同值子树是指该子树的所有节点都拥有相同的数值。

难度：中等

示例：

输入:
    5
   / \
  1   5
 / \   \
5   5   5

输出: 4
解释: 有4个子树的所有节点都有相同的值:
      1. 叶子节点 "5" (左边)
      2. 叶子节点 "5" (中间)
      3. 叶子节点 "5" (右边)
      4. 节点 "5" 及其右子树 (右边)

解题思路

这个问题可以通过后序遍历（Post-order Traversal）二叉树来解决。我们需要从叶子节点开始判断，逐步向上构建结果。

关键思路

叶子节点自身就是一个同值子树。
非叶子节点需要满足以下条件才能形成同值子树：
- 它的所有子节点都是同值子树
- 如果有左子节点，左子节点的值必须与当前节点相同
- 如果有右子节点，右子节点的值必须与当前节点相同

解题步骤

使用后序遍历访问二叉树的节点。
对于每个节点，检查它是否能形成同值子树：
- 如果节点为空，返回true（空节点被视为同值子树，但不计数）。
- 递归判断左子树和右子树是否为同值子树。
- 检查节点值与其子节点的值是否相同（如果存在子节点）。
如果当前节点形成了同值子树，将计数器加1。
返回最终的计数结果。

代码实现

C#实现

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    private int count = 0;
    
    public int CountUnivalSubtrees(TreeNode root) {
        IsUnivalSubtree(root);
        return count;
    }
    
    // 判断一个节点及其子树是否为同值子树
    private bool IsUnivalSubtree(TreeNode node) {
        // 空节点视为同值子树，但不增加计数
        if (node == null) {
            return true;
        }
        
        // 后序遍历：先处理左右子树
        bool isLeftUnival = IsUnivalSubtree(node.left);
        bool isRightUnival = IsUnivalSubtree(node.right);
        
        // 当前节点不是同值子树的情况
        if (!isLeftUnival || !isRightUnival) {
            return false;
        }
        
        // 检查当前节点与子节点的值是否相同
        if (node.left != null && node.val != node.left.val) {
            return false;
        }
        
        if (node.right != null && node.val != node.right.val) {
            return false;
        }
        
        // 当前节点是同值子树，增加计数
        count++;
        return true;
    }
}

Python实现

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def countUnivalSubtrees(self, root: Optional[TreeNode]) -> int:
        self.count = 0
        self.is_unival_subtree(root)
        return self.count
    
    def is_unival_subtree(self, node: Optional[TreeNode]) -> bool:
        # 空节点视为同值子树，但不增加计数
        if not node:
            return True
        
        # 后序遍历：先处理左右子树
        is_left_unival = self.is_unival_subtree(node.left)
        is_right_unival = self.is_unival_subtree(node.right)
        
        # 当前节点不是同值子树的情况
        if not is_left_unival or not is_right_unival:
            return False
        
        # 检查当前节点与子节点的值是否相同
        if node.left and node.val != node.left.val:
            return False
        
        if node.right and node.val != node.right.val:
            return False
        
        # 当前节点是同值子树，增加计数
        self.count += 1
        return True

C++实现

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int countUnivalSubtrees(TreeNode* root) {
        int count = 0;
        isUnivalSubtree(root, count);
        return count;
    }
    
private:
    bool isUnivalSubtree(TreeNode* node, int& count) {
        // 空节点视为同值子树，但不增加计数
        if (!node) {
            return true;
        }
        
        // 后序遍历：先处理左右子树
        bool isLeftUnival = isUnivalSubtree(node->left, count);
        bool isRightUnival = isUnivalSubtree(node->right, count);
        
        // 当前节点不是同值子树的情况
        if (!isLeftUnival || !isRightUnival) {
            return false;
        }
        
        // 检查当前节点与子节点的值是否相同
        if (node->left && node->val != node->left->val) {
            return false;
        }
        
        if (node->right && node->val != node->right->val) {
            return false;
        }
        
        // 当前节点是同值子树，增加计数
        count++;
        return true;
    }
};

性能分析

时间复杂度

我们需要访问树中的每个节点一次，因此时间复杂度为 O(n)，其中 n 是树中节点的数量。

空间复杂度

递归调用使用的栈空间取决于树的高度，最坏情况下（树是一个链表）为 O(n)。
平均情况下，对于平衡二叉树，空间复杂度为 O(log n)。

解法优化

方法一：自底向上（上述实现）

我们已经实现了自底向上的解法，通过后序遍历判断每个子树是否为同值子树。

方法二：带返回值的后序遍历

可以修改递归函数，使其不仅返回是否为同值子树，还返回子树的值（如果它是同值子树），这样可以简化判断逻辑。

def countUnivalSubtrees(self, root: Optional[TreeNode]) -> int:
    self.count = 0
    
    def dfs(node):
        if not node:
            return True, None  # 空节点是同值子树，值为None
        
        is_left_unival, left_val = dfs(node.left)
        is_right_unival, right_val = dfs(node.right)
        
        # 如果左右子树都是同值子树，且当前节点与子节点值相同（如果存在）
        if (is_left_unival and is_right_unival and
            (not node.left or node.val == left_val) and
            (not node.right or node.val == right_val)):
            self.count += 1
            return True, node.val
        
        return False, None
    
    dfs(root)
    return self.count

方法三：使用全局变量标记

另一种优化是使用一个“dummy”值（例如，无穷大）来表示非同值子树，这样可以简化代码：

int countUnivalSubtrees(TreeNode* root) {
    int count = 0;
    dfs(root, count);
    return count;
}

bool dfs(TreeNode* node, int& count) {
    if (!node) return true;
    
    bool left = dfs(node->left, count);
    bool right = dfs(node->right, count);
    
    if ((!left || (node->left && node->left->val != node->val)) ||
        (!right || (node->right && node->right->val != node->val))) {
        return false;
    }
    
    count++;
    return true;
}

代码亮点

后序遍历：通过后序遍历，我们可以自底向上地判断每个子树是否为同值子树。
递归实现：代码简洁明了，体现了问题的递归性质。
标记技术：使用布尔返回值标记子树是否为同值子树，避免重复计算。
空节点处理：将空节点视为同值子树（但不计数），简化了边界情况的处理。

常见错误

忘记检查子节点值：需要检查当前节点与其子节点的值是否相同。
忘记增加计数：当确认一个节点是同值子树时，别忘了增加计数。
错误理解同值子树：同值子树要求所有节点都具有相同的值，而不仅仅是当前节点与其直接子节点。