Straightforward DFS Java Solution with detailed explanation


  • 2

    Get the sum of whole tree and the sum of each subtree. Then check whether one of the sum of a subtree equals the total sum - the sum of this subtree

    class Solution {
        private boolean ans = false;
        List<Integer> list = new ArrayList<>();// record sum of each subtree
        public boolean checkEqualTree(TreeNode root) {
            if(root==null) return false;
            if(root.left==null&&root.right==null) return false;
            int sum = dfs(root);
            if(sum==0){
                int count = 0;
                for(int num : list){
                    if(num==0){
                        count++;
                    }
                }
                return count>=2;// check whether there are at least 1 subtress whose sum == 0 so that the other part is also 0. 
    //Then the tree could be divided into 2 eqivalent parts.
            }
            for(int num : list){
                if(num==sum-num){// if the sum of this subtree == total sum - sum of itself, this means the sum of two parts are equal
                    return true;
                }
            }
            return false;
        }
        public int dfs(TreeNode root){
            if(root==null) return 0;
            int cur = root.val;
            int left = dfs(root.left);
            int right = dfs(root.right);
            int sum = cur+left+right;
            list.add(sum);
            return sum;
        }
    }
    

  • 0
    A

    @wxl163530 code will not work for [0,-1,1]....you need to remove the last element from the arraylist for it to work....


  • 1

    @ares_1197 You r right, recently they add some new test case. I have already updated the most recent version of my solution


  • 0
    boolean result = false;
    public boolean checkEqualTree(TreeNode root) {
        long sum = total(root, 0);
        if(sum % 2 != 0) return false;
        
        result = false;
        total(root, sum);
        return result;
    }
    private long total(TreeNode root, long sum) {
        if(root == null) return 0;
        if(root.left == null && root.right == null) return root.val;
        long left = total(root.left, sum);
        long right = total(root.right, sum);
        if((root.left!= null && left == sum/2) || (root.right != null && right == sum/2)) {
            result = true;
        }
        return root.val + left + right;
    }

Log in to reply
 

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