Skip to content

663. Equal Tree Partition 👍

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
 public:
  bool checkEqualTree(TreeNode* root) {
    if (root == nullptr)
      return false;

    unordered_set<int> seen;
    const int sum = root->val + dfs(root->left, seen) + dfs(root->right, seen);
    return sum % 2 == 0 && seen.contains(sum / 2);
  }

 private:
  int dfs(TreeNode* root, unordered_set<int>& seen) {
    if (root == nullptr)
      return 0;

    const int sum = root->val + dfs(root->left, seen) + dfs(root->right, seen);
    seen.insert(sum);
    return sum;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
  public boolean checkEqualTree(TreeNode root) {
    if (root == null)
      return false;

    Set<Integer> seen = new HashSet<>();
    final int sum = root.val + dfs(root.left, seen) + dfs(root.right, seen);
    return sum % 2 == 0 && seen.contains(sum / 2);
  }

  private int dfs(TreeNode root, Set<Integer> seen) {
    if (root == null)
      return 0;

    final int sum = root.val + dfs(root.left, seen) + dfs(root.right, seen);
    seen.add(sum);
    return sum;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution:
  def checkEqualTree(self, root: TreeNode | None) -> bool:
    if not root:
      return False

    seen = set()

    def dfs(root: TreeNode | None) -> int:
      if not root:
        return 0

      summ = root.val + dfs(root.left) + dfs(root.right)
      seen.add(summ)
      return summ

    summ = root.val + dfs(root.left) + dfs(root.right)
    return summ % 2 == 0 and summ // 2 in seen