0663：均匀树划分（★）

力扣第 663 题

题目

给定一棵有 n 个结点的二叉树，你的任务是检查是否可以通过去掉树上的一条边将树分成两棵，且这两棵树结点之和相等。

样例 1:

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

输出: True
解释:
5
/
10

和: 15

10
/  \
2    3

和: 15

样例 2:

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

输出: False
解释: 无法通过移除一条树边将这棵树划分成结点之和相等的两棵子树。

注释 :

1. 树上结点的权值范围 [-100000, 100000]。
2. 1 <= n <= 10000

分析

等价于找一个非根节点，其子树和是整个树之和的一半。

因此深搜返回子树和并记录即可。注意根节点不能算。

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

def checkEqualTree(self, root) -> bool:
	def dfs(node):
		if not node:
			return 0
		s = node.val+dfs(node.left)+dfs(node.right)
		if node is not root:
			vis.add(s)
		return s
	
	vis = set()
	total = dfs(root)
	return total/2 in vis

时间 O(N)，68 ms