题目描述：

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:

1. The range of tree node value is in the range of [-100000, 100000].
2. 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/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码