Simple Java solution with Set but not Map. 中文版


  • 0
    B

    一开始用Set存,发现[0,-1,1]不对,这是因为我们的递归把整颗树的和存入了Set,如果恰好树总和是0,那么0/2也一定也已经被存在Set里了. 那么其实只要先不存整个树的和就好了.

    We can actually use Set to store subtree sums, but remember not to store the total tree sum into the Set for edge case like [0, -1, 1]

        public boolean checkEqualTree(TreeNode root) {
            if (root == null) return false;
            Set<Integer> set = new HashSet<>();
            int left = treeSum(root.left, set);
            int right = treeSum(root.right, set);
            int sum = root.val + left + right;
            return sum % 2 == 0 && sumset.contains(sum/2);
            
        }
        
        public int treeSum(TreeNode root, Set<Integer> set) {
            if (root == null) return 0;
            int sum = root.val + treeSum(root.left, set) + treeSum(root.right, set);
            set.add(sum);
            return sum;
        }
    

Log in to reply
 

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