forked from shijbian/LeetCode
-
Notifications
You must be signed in to change notification settings - Fork 1
Expand file tree
/
Copy pathequal-tree-partition.py
More file actions
30 lines (27 loc) · 824 Bytes
/
equal-tree-partition.py
File metadata and controls
30 lines (27 loc) · 824 Bytes
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
# Time: O(n)
# Space: O(n)
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def checkEqualTree(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
def getSumHelper(node, lookup):
if not node:
return 0
total = node.val + \
getSumHelper(node.left, lookup) + \
getSumHelper(node.right, lookup)
lookup[total] += 1
return total
lookup = collections.defaultdict(int)
total = getSumHelper(root, lookup)
if total == 0:
return lookup[total] > 1
return total%2 == 0 and (total/2) in lookup