Java solution, Tree traversal and Sum


  • 5
    class Solution {
        boolean equal = false;
        long total = 0;
        
        public boolean checkEqualTree(TreeNode root) {
            if (root.left == null && root.right == null) return false;
            total = getTotal(root);
            checkEqual(root);
            return equal;
        }
        
        private long getTotal(TreeNode root) {
            if (root == null) return 0;
            return getTotal(root.left) + getTotal(root.right) + root.val;
        }
        
        private long checkEqual(TreeNode root) {
            if (root == null || equal) return 0;
            
            long curSum = checkEqual(root.left) + checkEqual(root.right) + root.val;
            if (total - curSum == curSum) {
                equal = true;
                return 0;
            }
            return curSum;
        }
    }
    

  • 3

    C++ solution. Same idea but a different approach. I store the subtree sum at each node while calculating the total sum to avoid checking the entire subtree later.

    /**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution {
    public:
        bool checkEqualTree(TreeNode* root) {
            if (!root->left && !root->right) return false;
            int sum = sumTree(root);
            return checkEqual(root, sum);
        }
        
        bool checkEqual(TreeNode* root, int sum){
            if (!root) return false;
            if (sum-2*root->val==0)
                return true;
            
            return checkEqual(root->left, sum) || checkEqual(root->right, sum);
        }
        
        int sumTree(TreeNode* root){
            if (!root) return 0;
            root->val += sumTree(root->left) + sumTree(root->right);
            return root->val;
        }
    };
    

  • 0
    M
    This post is deleted!

  • 0
    S

    Iterative version. DFS. Same idea.

    class Solution {
        public boolean checkEqualTree(TreeNode root) {
            if(root == null) return false;
            int sum = sumTree(root);
            Stack<TreeNode> stk = new Stack<TreeNode>();
            stk.push(root);
            while(!stk.isEmpty()){
            	TreeNode node = stk.pop();
            	if(node.left != null) {
                	int leftVal = sumTree(node.left);
                	if(leftVal == sum - leftVal) return true;
            		stk.push(node.left);
            	}
            	if(node.right != null) {
                	int rightVal = sumTree(node.right);
                	if(rightVal == sum - rightVal) return true; 
                	stk.push(node.right);
            	}
            }
            return false;
        }
        private int sumTree(TreeNode root){
        	if(root == null) return 0;
        	int res = root.val + sumTree(root.left) + sumTree(root.right);
        	return res;
        }
    }
    

  • 0
    B

    Same thing I did. You can eliminate the cases at the beginning just buy checking whether the total is odd.
    Since it is impossible to have equal partitions in that case.


  • 0
    A

    @shawngao I had a very similar approach and it seems like our solution failed the test case [0,1,-1]. Note the fix in the comment.

    class Solution {
        boolean res = false;
        TreeNode head;    // Original root of the tree
        
        public boolean checkEqualTree(TreeNode root) {
            if (root == null || (root.left == null && root.right == null))   return false;
            int sum = sum(root);
            if (sum % 2 != 0)   return false;
            
            head = root;
            helper(root, sum / 2);
             
            return res;
        }
        
        int helper(TreeNode root, int target) {
            if (root == null || res)   return 0;
            
            int left = helper(root.left, target);
            int right = helper(root.right, target);
            
            if (root != head &&     // FIX: Check if current root is original root of tree
                root.val + left + right == target) {
                res = true;
                return 0;
            }
            return root.val + left + right;
        }
        
        public int sum(TreeNode root) {
            if (root == null)   return 0;
            return root.val + sum(root.left) + sum(root.right);
        }    
    }
    

  • 1
    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;
    }

  • 0
    D

    @shawngao This solution is failed for case [0, -1, 1].


  • 0
    W

    @Darrenli yes, this solution failed for case [0,-1,1], and failed [1, -1] as well

    0                  1
    

    -1 1 -1


Log in to reply
 

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