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


b'
\n
\n\n
\n

Approach #1: Depth-First Search [Accepted]

\n

Intuition and Algorithm

\n

After removing some edge from parent to child, (where the child cannot be the original root) the subtree rooted at child must be half the sum of the entire tree.

\n

Let\'s record the sum of every subtree. We can do this recursively using depth-first search. After, we should check that half the sum of the entire tree occurs somewhere in our recording (and not from the total of the entire tree.)

\n

Our careful treatment and analysis above prevented errors in the case of these trees:

\n
  0\n / \\\n-1  1\n\n 0\n  \\\n   0\n
\n\n

Complexity Analysis

\n
    \n
  • \n

    Time Complexity: where is the number of nodes in the input tree. We traverse every node.

    \n
    • \n
  • \n

    Space Complexity: , the size of seen and the implicit call stack in our DFS.

    \n
    • \n
\n
\n

Analysis written by: @awice.

\n
'