二叉树灯饰

The solution employs a dynamic programming approach using depth-first search (DFS) to determine the minimum number of switch operations needed to turn off all the lights in a binary tree. At each node, four states are computed, representing the minimum operations required for different configurations: 1) all lights on, 2) all lights off, 3) only the current node light on, and 4) only the current node light off. These states are computed based on the node's current state (light on or off) and the minimal operations required for its children's states. The recursive DFS function calculates the optimal switch operations for each state by combining results from left and right children and considering all possible switch actions at the current node.

时间复杂度: O(n)

空间复杂度: O(h) where h is the height of the tree, worst-case O(n)

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def closeLampInTree(self, root: TreeNode) -> int:
        # Recursive DFS to compute the minimal switch operations for each node's states
        def dfs(c):
            if not c:
                return 0,0,0,0 # Base case: if current node is None, return zero operations for all states
            # Recurse on left and right children
            l1,l2,l3,l4 = dfs(c.left)
            r1,r2,r3,r4 = dfs(c.right)
            # Calculate min operations for each state based on current node's light status
            if c.val: # If current node's light is on
                t1 = min(l1 + r1, 2 + l2 + r2, 2 + l3 + r3, 2 + l4 + r4) # all lights on
                t2 = min(1 + l2 + r2, l1 + r1 + 1, l3 + r3 + 1, l4 + r4 + 3) # all lights off
                t3 = min(l1 + r1 + 2, l2 + r2, l3 + r3 + 2, l4 + r4 + 2) # current on, others off
                t4 = min(l1 + r1 + 1, l2 + r2 + 1, l3 + r3 + 3, l4 + r4 + 1) # current off, others on
            else: # If current node's light is off
                t1 = min(l1 + r1 + 1, 1 + l2 + r2, 3 + l3 + r3, 1 + l4 + r4) # all lights on
                t2 = min(l2 + r2, l1 + r1 + 2, l3 + r3 + 2, l4 + r4 + 2) # all lights off
                t3 = min(l1 + r1 + 1, l2 + r2 + 1, l3 + r3 + 1, l4 + r4 + 3) # current on, others off
                t4 = min(l1 + r1, l2 + r2 + 2, l3 + r3 + 2, l4 + r4 + 2) # current off, others on
            return t1, t2, t3, t4 # Return calculated states
        # Start DFS from the root
        ans = dfs(root)
        return ans[1] # Return the minimum operations to turn all lights off