share my java solution!


  • 0
    T
    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        public boolean checkEqualTree(TreeNode root) {
             if(root == null || (root.left==null&&root.right==null)) {
                 return false;
             }   
             int sum = getSum(root);
             if(sum%2!=0){
                return false;
             }
             Map<TreeNode,Integer> map = new HashMap<>();
             
             return canPartition(root.left,map,sum/2) || canPartition(root.right,map,sum/2);
             
        }
        
        public boolean canPartition(TreeNode root,Map<TreeNode,Integer> map,int target){
            if(root==null){
                return false;
            }else if(root.left==null&&root.right==null){
                 map.put(root,root.val);
                if(root.val==target){
                    return true;
                }else{
                    return false;
                }
            }
            int sum = root.val;
            if(canPartition(root.left,map,target)){
                return true;
            }else if(root.left!=null){
                sum+=map.get(root.left);
            }
            
            
            if(canPartition(root.right,map,target)){
                return true;
            }else if(root.right!=null){
                sum+=map.get(root.right);
            }
            
            map.put(root,sum);
            return sum==target;
        }
        
        public int getSum(TreeNode root){
            if(root==null) return 0;
            int sum = getSum(root.left)+getSum(root.right);
            return sum+root.val;
        }
    }
    

    Here is my another version of Java Solution, just change map into array:

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        public boolean checkEqualTree(TreeNode root) {
             if(root == null || (root.left==null&&root.right==null)) {
                 return false;
             }   
             int sum = getSum(root);
             if(sum%2!=0){
                return false;
             }
             //Map<TreeNode,Integer> map = new HashMap<>();
             
             return canPartition(root.left,new int[1],sum/2) || canPartition(root.right,new int[1],sum/2);
             
        }
        
        public boolean canPartition(TreeNode root,int[] sum,int target){
            if(root==null){
                return false;
            }else if(root.left==null&&root.right==null){
                sum[0]=root.val;
                if(root.val==target){
                    return true;
                }else{
                    return false;
                }
            }
            sum[0] = root.val;
            int[] left_sum = new int[1];
            int[] right_sum = new int[1];
            if(canPartition(root.left,left_sum,target)){
                return true;
            }else if(root.left!=null){
                sum[0]+=left_sum[0];
            }
            
            
            if(canPartition(root.right,right_sum,target)){
                return true;
            }else if(root.right!=null){
                sum[0]+=right_sum[0];
            }
            
            return sum[0]==target;
        }
        
        public int getSum(TreeNode root){
            if(root==null) return 0;
            int sum = getSum(root.left)+getSum(root.right);
            return sum+root.val;
        }
    }
    

Log in to reply
 

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