Java O(n*n) and O(n) time complexity solutions.


  • 0
    C
    // top-down, O(n*n) time
    public int countUnivalSubtrees1(TreeNode root) {
        int ret = 0;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if (node != null) {
                ret += isUni(node)?1:0;
                queue.add(node.left);
                queue.add(node.right);
            }
        }
        return ret;
    }
    
    private boolean isUni(TreeNode root) {
        if (root == null) {
            return true;
        }
        return isUni(root.left) && isUni(root.right) && 
        (root.left == null || root.left.val == root.val) && 
        (root.right == null || root.right.val == root.val);
    }
    
    // O(n) time, time complexity just like post-order travesal
    int count = 0;
    public int countUnivalSubtrees(TreeNode root) {
        checkUni(root);
        return count;
    }
    
    private boolean checkUni(TreeNode root) {
        if (root == null) {
            return true;
        }
        boolean l = checkUni(root.left);
        boolean r = checkUni(root.right);
        if (l && r && (root.left == null || root.left.val == root.val) && 
        (root.right == null || root.right.val == root.val)) {
            count++;
            return true;
        }
        return false;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.