# LeetCode: 663. 均匀树划分¶

## 1、题目描述¶

输入:
5
/ \
10 10
/  \
2   3

5
/
10

10
/  \
2    3



输入:
1
/ \
2  10
/  \
2   20



• 树上结点的权值范围 [-100000, 100000]
• $1 <= n <= 10000$

## 2、解题思路¶

• 尝试断开每个节点的左右节点进行判断
• 向下传递当前节点父节点之上的和值以及兄弟树的值
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

from functools import lru_cache

class Solution:
def checkEqualTree(self, root: TreeNode) -> bool:
@lru_cache(None)
def get_sum(node):
if not node:
return 0
return node.val + get_sum(node.left) + get_sum(node.right)

ans = False

def dfs(node, cur_sum):
nonlocal ans
if ans or not node or (not node.left and not node.right):
return
if node.left and node.val + cur_sum + get_sum(node.right) == get_sum(node.left):
ans = True
if node.left and (node.left.left or node.left.right):
dfs(node.left, node.val + cur_sum + get_sum(node.right))

if node.right and node.val + cur_sum + get_sum(node.left) == get_sum(node.right):
ans = True
if node.right and (node.right.left or node.right.right):
dfs(node.right, node.val + cur_sum + get_sum(node.left))

dfs(root, 0)
return ans