>>> distribute_coins(TreeNode(3, TreeNode(0), TreeNode(0))) 2 >>> distribute_coins(TreeNode(0, TreeNode(3), TreeNode(0))) 3 >>> distribute_coins(TreeNode(0, TreeNode(0), TreeNode(3))) 3 >>> distribute_coins(None) 0 >>> distribute_coins(TreeNode(0, TreeNode(0), Tr
(root: TreeNode | None)
| 56 | |
| 57 | |
| 58 | def distribute_coins(root: TreeNode | None) -> int: |
| 59 | """ |
| 60 | >>> distribute_coins(TreeNode(3, TreeNode(0), TreeNode(0))) |
| 61 | 2 |
| 62 | >>> distribute_coins(TreeNode(0, TreeNode(3), TreeNode(0))) |
| 63 | 3 |
| 64 | >>> distribute_coins(TreeNode(0, TreeNode(0), TreeNode(3))) |
| 65 | 3 |
| 66 | >>> distribute_coins(None) |
| 67 | 0 |
| 68 | >>> distribute_coins(TreeNode(0, TreeNode(0), TreeNode(0))) |
| 69 | Traceback (most recent call last): |
| 70 | ... |
| 71 | ValueError: The nodes number should be same as the number of coins |
| 72 | >>> distribute_coins(TreeNode(0, TreeNode(1), TreeNode(1))) |
| 73 | Traceback (most recent call last): |
| 74 | ... |
| 75 | ValueError: The nodes number should be same as the number of coins |
| 76 | """ |
| 77 | |
| 78 | if root is None: |
| 79 | return 0 |
| 80 | |
| 81 | # Validation |
| 82 | def count_nodes(node: TreeNode | None) -> int: |
| 83 | """ |
| 84 | >>> count_nodes(None) |
| 85 | 0 |
| 86 | """ |
| 87 | if node is None: |
| 88 | return 0 |
| 89 | |
| 90 | return count_nodes(node.left) + count_nodes(node.right) + 1 |
| 91 | |
| 92 | def count_coins(node: TreeNode | None) -> int: |
| 93 | """ |
| 94 | >>> count_coins(None) |
| 95 | 0 |
| 96 | """ |
| 97 | if node is None: |
| 98 | return 0 |
| 99 | |
| 100 | return count_coins(node.left) + count_coins(node.right) + node.data |
| 101 | |
| 102 | if count_nodes(root) != count_coins(root): |
| 103 | raise ValueError("The nodes number should be same as the number of coins") |
| 104 | |
| 105 | # Main calculation |
| 106 | def get_distrib(node: TreeNode | None) -> CoinsDistribResult: |
| 107 | """ |
| 108 | >>> get_distrib(None) |
| 109 | namedtuple("CoinsDistribResult", "0 2") |
| 110 | """ |
| 111 | |
| 112 | if node is None: |
| 113 | return CoinsDistribResult(0, 1) |
| 114 | |
| 115 | left_distrib_moves, left_distrib_excess = get_distrib(node.left) |
nothing calls this directly
no test coverage detected