250. Count Univalue Subtrees

1455 단어
Given a binary tree, count the number of uni-value subtrees. A Uni-value subtree means all nodes of the subtree have the same value. For example: Given binary tree,
              5
             / \
            1   5
           / \   \
          5   5   5

return 4.

Solution:post-order 분할 upwards 업로드


사고방식: Divide: left sub and right sub Conquer: ifSame(boolean left, boolean right), int count, and then uploads Time Complexity: T(N) = 2T(N/2) + O(1) = > O(N) Space Complexity: O(N)
Solution Code:
public class Solution {
    public int countUnivalSubtrees(TreeNode root) {
        int[] count = new int[1];
        helper(root, count);
        return count[0];
    }
    
    private boolean helper(TreeNode node, int[] count) {
        if (node == null) return true;

        // divide
        boolean left = helper(node.left, count);
        boolean right = helper(node.right, count);
        
        // conquer (ifSame(boolean left, boolean right), int count), 
        // and uploads ifSame & count 
        if (left && right) {
            if (node.left != null && node.val != node.left.val) {
                return false;
            }
            if (node.right != null && node.val != node.right.val) {
                return false;
            }
            count[0]++;
            return true;
        }
        return false;
    }
}

좋은 웹페이지 즐겨찾기