Home
Algorithms Data Structures Interview Experiences
Amazon Google Facebook Microsoft Apple Netflix
Play 2048 How to

LeetCode Solutions

663. Equal Tree Partition

Time: $O(n)$

Space: $O(n)$

			


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.count(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;
  }
};




			


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;
  }
}




			


class Solution:
  def checkEqualTree(self, root: Optional[TreeNode]) -> bool:
    if not root:
      return False

    seen = set()

    def dfs(root: Optional[TreeNode]) -> 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