250. Count Univalue Subtrees

Leetcode

https://leetcode.com/problems/count-univalue-subtrees/

題目

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 1:

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

what is univalue ?

If the node meets one of the following criteria:

1. The node has no children (base case)

2. All of the node's children are univalue subtrees, and the node and its children all have the same value

解答

• 方法一

var countUnivalSubtrees = function(root) {
    let count = 0;
    
    const helper = (node) => {
        if (!node) return [true];
        
        const val = node.val;
        
        if (!node.left && !node.right) {
            count++;
            return [true, val]
        }
        
        // node.left 是 null 的話，預設帶 leftValue 等於本身的 val
        const [isLeftUnival, leftValue = val] = helper(node.left);
        const [isRightUnival, rightValue = val] = helper(node.right);
        const isValueSame = val === leftValue && val === rightValue;
        const isUniVal = isLeftUnival && isRightUnival && isValueSame;
        if (isUniVal) count++;
        
        return [isUniVal, val]
    }
    
    helper(root);
    return count;
};

Runtime: 117 ms, faster than 20.31% of JavaScript online submissions for Count Univalue Subtrees.

Memory Usage: 45.3 MB, less than 7.08% of JavaScript online submissions for Count Univalue Subtrees.

• 方法二

var countUnivalSubtrees = function(root) {
    let count = 0;
    
    const isUnival = (node, parentVal) => {
        if (!node) return true;
        
        const nodeVal = node.val;
        const conditions = [isUnival(node.left, nodeVal), isUnival(node.right, nodeVal)];
        // 使用 every 確保左右的節點都跑完 isUnival function
        if (!conditions.every(condition => condition)) {
           return false; 
        }
        
        // 左右節點都是 isUnival 的話就可以 count+1 了
        count++;
        return nodeVal === parentVal;
    }
    
    // 初始值帶入超過上限 1000 的 parentVal
    isUnival(root, 1001);
    return count;
};

Runtime: 72 ms, faster than 90.15% of JavaScript online submissions for Count Univalue Subtrees.

Memory Usage: 44.9 MB, less than 24.00% of JavaScript online submissions for Count Univalue Subtrees.