Leetcode # 1145. Binary Tree Coloring Game

https://leetcode.com/problems/binary-tree-coloring-game

Solution

Time Complexity: O(len(tree))
Space Complexity: O(len(tree))
(The input and output generally do not count towards the space complexity.)

class Solution:
  def btreeGameWinningMove(self, root: Optional[TreeNode], n: int, x: int) -> bool:
    stack = [root]
    while stack:
      cur = stack.pop()
      # ... 
      if cur.val == x:
        first_x = cur
        break
      
      for child in [cur.left, cur.right]:
        if child:
          stack.append(child)
    
    subtree_n = [0] * 2
    for i, subtree in enumerate([first_x.left, first_x.right]):
      stack = [subtree] if subtree else []
      while stack:
        cur = stack.pop()
        # ... 
        subtree_n[i] += 1
      
        for child in [cur.left, cur.right]:
          if child:
            stack.append(child)
    non_child_n = n - 1 - sum(subtree_n)
    return max([non_child_n] + subtree_n) > (n - 1) / 2

Last Updated on 2023/08/16 by A1go