[Java/C++] Simple solution with only one HashMap<>.


  • 32

    The idea is to use a hash table to record all the different sums of each subtree in the tree. If the total sum of the tree is sum, we just need to check if the hash table constains sum/2.

    The following code has the correct result at a special case when the tree is [0,-1,1], which many solutions dismiss. I think this test case should be added.

    Java version:

        public boolean checkEqualTree(TreeNode root) {
            Map<Integer, Integer> map = new HashMap<Integer, Integer>();
            int sum = getsum(root, map);
            if(sum == 0)return map.getOrDefault(sum, 0) > 1;
            return sum%2 == 0 && map.containsKey(sum/2);
        }
        
        public int getsum(TreeNode root, Map<Integer, Integer> map ){
            if(root == null)return 0;
            int cur = root.val + getsum(root.left, map) + getsum(root.right, map);
            map.put(cur, map.getOrDefault(cur,0) + 1);
            return cur;
        }
            
    

    C++ version:

        bool checkEqualTree(TreeNode* root) {
            unordered_map<int, int> map;
            int sum = getsum(root, map);
            if(sum == 0)return map[sum] > 1;
            return sum%2 == 0 && map.count(sum/2);
        }
        
        int getsum(TreeNode* root,  unordered_map<int, int>& map){
            if(root == NULL)return 0;
            int cur = root->val + getsum(root->left, map) + getsum(root->right, map);
            map[cur]++;
            return cur;
        }
        
    

  • 1
    A

    Excellent solution. For some reason, I tried to remove each edge and compare the two resulting sums. I overlooked the obvious that I simply needed to look for sum/2.


  • 0

    @ameem91 Thanks! You can also see 416. Partition Equal Subset Sum, which is similar with this one.


  • 0
    L

    @Hao-Cai very smart and clean solution!


  • 0
    This post is deleted!

  • 0

    Very smart idea and very concise code!


  • 0
    W

    Good idea double click 666


  • 0
    A

    @Hao-Cai You said a solution should pass the following test case: [0, -1, 1]. Why do you say this is so? There are exactly two edges, one between 0 and -1 and one between 0 and 1, so if you are to remove exactly one edge, your sums will either be -1 and 1 or 1 and -1. Thus, there does not exist an edge that fulfills the criteria in the problem statement.


  • 0

    @aznkid66 The "pass" means the output of the code is correct...


  • 0

    @Hao-Cai I originally had the same idea as you, but later on I also found that if the total root.val = 0 and it's leftchild sum = -k, right child sum = k, we will always return true cuz root node has sum/2=0...

    So I think we should not add the root-sum into HashMap, that will solve the problem. In fact under any circumstances, we do not expect to cut the root node:)

    public boolean checkEqualTree(TreeNode root) {
        Map<Integer,TreeNode> map = new HashMap<Integer,TreeNode>();
        int sum = TreeSum(root,map,root);
        if(sum/1.0/2!=sum/2) return false;//in case sum/2 is not integer
        return map.get(sum/2)!=null;//check wether we have node of sum/2
    }
    public int TreeSum(TreeNode node, Map<Integer,TreeNode> map,TreeNode root){
        if(node==null) return 0;
        int sum = node.val+TreeSum(node.left, map, root)+TreeSum(node.right, map, root);
        if(node!=root) map.put(sum,node);
        return sum;
    }

  • 0

    @tongzhou2 Thanks for your comments! My code also returns false when the tree is [0,-1,1] (in the 3rd line ). "not add the root-sum into HashMap" is also an excellent ideal, and you can use a hashset<> instead of a hashmap<>.


  • 0

    @Hao-Cai Ya I use HashMap cuz I was thinking to return the node where we should cut the tree:)


  • 0
    F

    @Hao-Cai said in [Java/C++] Simple solution with only one HashMap<>.:

    correct result at a sp

    what about -1
    -1 1
    1
    The sum is 0, but you can actually split into 2 subtree?


  • 0

    @fuqianran what's the tree? you can clear it using an array.


  • 0
    B

    @ameem91 Same here, did not think of the dividing by 2.


  • 0
    A

    Great solution, check out mine with. I use no extra space and have O(n) runtime


  • 0
    Z

    Brilliant solution!


  • 0
    L

    Hi Vincent,

    Thanks for your nice solution!

    I used a similar way as you to record all the different sums of each subtree in the tree. And I used an ArrayList rather than HashMap to treat the special case like [0,-1,1]. As the sum of the entire tree is calculated on the root, it would be the last element to be added to the ArrayList. So we can just loop to the second last element to avoid reach the root sum. This implementation avoids recording the frequency of each sum. Just for reference.

    class Solution {
        public boolean checkEqualTree(TreeNode root) {
            ArrayList<Integer> treeSumList = new ArrayList<>();
            int totalSum = treeSumHelper(root, treeSumList);
            if (totalSum % 2 != 0) return false;
            else {
                for (int i = 0; i < treeSumList.size() - 1; i++) // root sum is the last element
                    if (treeSumList.get(i) == totalSum / 2) return true;
            }
            return false;
        }
        
        private int treeSumHelper(TreeNode root, ArrayList<Integer> treeSumList) {
            if (root == null) return 0;
            int nodeSum = root.val + treeSumHelper(root.left, treeSumList) + treeSumHelper(root.right, treeSumList);
            treeSumList.add(nodeSum);
            return nodeSum;
        }
    }
    

  • 0

    @lun_jiang Yes! Very smart approach!


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.