题目描述:
LeetCode 663. Equal Tree Partition
Given a binary tree with n
nodes, your task is to check if it's possible to partition the tree to two trees which have the equal sum of values after removing exactly one edge on the original tree.
Example 1:
Input: 5 / \ 10 10 / \ 2 3 Output: True Explanation: 5 / 10 Sum: 15 10 / \ 2 3 Sum: 15
Example 2:
Input: 1 / \ 2 10 / \ 2 20 Output: False Explanation: You can't split the tree into two trees with equal sum after removing exactly one edge on the tree.
Note:
- The range of tree node value is in the range of [-100000, 100000].
- 1 <= n <= 10000
题目大意:
给定二叉树,求是否存在一条边,将该边切断后得到的两个新二叉树的和相等。
解题思路:
递归求以各节点为根的子树的和
遍历各节点,判断该节点的子树和 * 2 == 根节点的节点和
Python代码:
# 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
"""
self.dmap = {}
def solve(n, c):
if not n: return 0
self.dmap[c] = n.val + solve(n.left, c * 2) + solve(n.right, c * 2 + 1)
return self.dmap[c]
solve(root, 1)
total = self.dmap[1]
del self.dmap[1]
return any(v * 2 == total for k, v in self.dmap.iteritems())
本文链接:http://bookshadow.com/weblog/2017/08/21/leetcode-equal-tree-partition/
请尊重作者的劳动成果,转载请注明出处!书影博客保留对文章的所有权利。