A greedy bottom-up traversal (post-order) lets you place cameras as far from the leaves as possible to maximize coverage.

Binary Tree Cameras

hard

Acceptance: 38%

Binary Tree

Place surveillance cameras on the nodes of a binary tree so that every node is observed. A camera on a node covers that node, its parent, and its direct children. Determine the smallest number of cameras required to cover every node in the tree.

Examples

Example 1:

Input:root = [0,0,null,0,null,0,0]

Output:2

Example 2:

Input:root = [0,0,0]

Output:1

Hints

1234567

import java.util.*;

public class Main {
    public static void main(String[] args) {
        // Write your solution here
    }
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        // Write your solution here
    }
}

Binary Tree Cameras

Examples

Hints

Related Problems