# 663     Equal Tree Partition

## 663. [Equal Tree Partition](https://leetcode.com/problems/equal-tree-partition/description/)

## 1. Question

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. Implementation

**(1) DFS**

```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean checkEqualTree(TreeNode root) {
        Map<Integer, Integer> map = new HashMap();
        int sum = getTreeSum(root, map);

        if (sum == 0) {
            return map.getOrDefault(sum, 0) >= 2;
        }

        return sum % 2 == 0 ? map.containsKey(sum / 2) : false;
    }

    public int getTreeSum(TreeNode node, Map<Integer, Integer> map) {
        if (node == null) {
            return 0;
        }

        int leftSum = getTreeSum(node.left, map);
        int rightSum = getTreeSum(node.right, map);

        int sum = node.val + leftSum + rightSum;
        map.put(sum, map.getOrDefault(sum, 0) + 1);
        return sum;
    }
}
```

## 3. Time & Space Complexity

DFS: 时间复杂度O(n), 空间复杂度O(k), k是map里不同sum的个数