250 Count Univalue Subtrees 统计同值子树

Description:

Given the root of a binary tree, return the number of uni-value subtrees.

A uni-value subtree means all nodes of the subtree have the same value.

Example:

Example 1:

[图片上传失败...(image-20ad3f-1667312129069)]

Input: root = [5,1,5,5,5,null,5]
Output: 4

Example 2:

Input: root = []
Output: 0

Example 3:

Input: root = [5,5,5,5,5,null,5]
Output: 6

Constraints:

The number of the node in the tree will be in the range [0, 1000].
-1000 <= Node.val <= 1000

题目描述：

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

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

示例：

输入: root = [5,1,5,5,5,null,5]

              5
             / \
            1   5
           / \   \
          5   5   5

输出: 4

思路：

递归后序遍历
当遍历到空结点时返回 true
先遍历左子树, 再遍历右子树, 最后遍历根结点
如果为叶子结点为 true, 计数器加 1
从叶子结点往上遍历, 子树值完全相同的计数器加 1
即左子树右子树和根结点值相等
时间复杂度为 O(n), 空间复杂度为 O(n), 最差情况树退化为链表

代码:

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) 
    {
        result = 0;
        dfs(root);
        return result;
    }
private:
    int result;
    
    bool dfs(TreeNode* root) 
    {
        if (!root) return true;
        bool left = dfs(root -> left), right = dfs(root -> right), cur = (!root -> left or root -> val == root -> left -> val) and (!root -> right or root -> val == root -> right -> val);
        if (cur and left and right) ++result;
        return cur and left and right;
    }
};

Java:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    private int result = 0;
    
    public int countUnivalSubtrees(TreeNode root) {
        dfs(root);
        return result;
    }
    
    private boolean dfs(TreeNode root) {
        if (root == null) return true;
        boolean left = dfs(root.left), right = dfs(root.right), cur = (root.left == null || root.val == root.left.val) && (root.right == null || root.val == root.right.val);
        if (cur && left && right) ++result;
        return cur && left && right;
    }
}

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:
        count = 0
        def dfs(root: Optional[TreeNode]) -> bool:
            nonlocal count
            if not root:
                return True
            left, right = dfs(root.left), dfs(root.right)
            count += (cur := (not root.left or root.val == root.left.val) and (not root.right or root.val == root.right.val)) and left and right
            return cur and left and right
        dfs(root)
        return count