JAVA. Simple solution with only HashSet<>


  • 0
    A

    This problem can be solved using only HashSet.
    The set only store sum of subtree on the left or right.
    It didn't save sum of whole tree, this will solve some cases like when sum is 0.

    class Solution {
        HashSet<Integer> set = new HashSet<Integer>();
        public boolean checkEqualTree(TreeNode root) {
            // count the total sum
            // and save partial sum into HashSet
            int sum = totalSum(root);
    
            // if any subtree contains half sum, return true.
            // this also take care of case when sum of tree is 0.
            if (sum % 2 == 0) {
                return set.contains(sum/2);
            }
            return false;
        }
        
        private int totalSum(TreeNode root){
            if (root == null) return 0;
            
            int left = 0;
            int right = 0;
            // update left or right sum.
            if (root.left != null) {
                left = totalSum(root.left);
                set.add(left);
            }
            
            if (root.right != null) {
                right = totalSum(root.right);
                set.add(right);
            }
            
            int sum = left+right+root.val;
            return sum;
        }
    }
    

Log in to reply
 

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